<!DOCTYPE HTML>
<html lang="en" class="sidebar-visible no-js coal">
    <head>
        <!-- Book generated using mdBook -->
        <meta charset="UTF-8">
        <title>Rsa attack - Andrew&#x27;s Blog</title>


        <!-- Custom HTML head -->
        
        <meta name="description" content="Andrew Ryan&#x27;s Blog">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="theme-color" content="#ffffff" />

        <link rel="icon" href="../../favicon.svg">
        <link rel="shortcut icon" href="../../favicon.png">
        <link rel="stylesheet" href="../../css/variables.css">
        <link rel="stylesheet" href="../../css/general.css">
        <link rel="stylesheet" href="../../css/chrome.css">

        <!-- Fonts -->
        <link rel="stylesheet" href="../../FontAwesome/css/font-awesome.css">
        <link rel="stylesheet" href="../../fonts/fonts.css">

        <!-- Highlight.js Stylesheets -->
        <link rel="stylesheet" href="../../highlight.css">
        <link rel="stylesheet" href="../../tomorrow-night.css">
        <link rel="stylesheet" href="../../ayu-highlight.css">

        <!-- Custom theme stylesheets -->
        <link rel="stylesheet" href="../../src/style/custom.css">

        <!-- MathJax -->
        <script async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
    </head>
    <body>
    <div id="body-container">
        <!-- Provide site root to javascript -->
        <script>
            var path_to_root = "../../";
            var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "coal" : "coal";
        </script>

        <!-- Work around some values being stored in localStorage wrapped in quotes -->
        <script>
            try {
                var theme = localStorage.getItem('mdbook-theme');
                var sidebar = localStorage.getItem('mdbook-sidebar');

                if (theme.startsWith('"') && theme.endsWith('"')) {
                    localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
                }

                if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
                    localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
                }
            } catch (e) { }
        </script>

        <!-- Set the theme before any content is loaded, prevents flash -->
        <script>
            var theme;
            try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
            if (theme === null || theme === undefined) { theme = default_theme; }
            var html = document.querySelector('html');
            html.classList.remove('no-js')
            html.classList.remove('coal')
            html.classList.add(theme);
            html.classList.add('js');
        </script>

        <!-- Hide / unhide sidebar before it is displayed -->
        <script>
            var html = document.querySelector('html');
            var sidebar = null;
            if (document.body.clientWidth >= 1080) {
                try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
                sidebar = sidebar || 'visible';
            } else {
                sidebar = 'hidden';
            }
            html.classList.remove('sidebar-visible');
            html.classList.add("sidebar-" + sidebar);
        </script>

        <nav id="sidebar" class="sidebar" aria-label="Table of contents">
            <div class="sidebar-scrollbox">
                <ol class="chapter"><li class="chapter-item affix "><a href="../../index.html">Andrew's Blog</a></li><li class="chapter-item "><a href="../../posts/linux/linux.html"><strong aria-hidden="true">1.</strong> Linux</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/linux/install_linux.html"><strong aria-hidden="true">1.1.</strong> install linux</a></li><li class="chapter-item "><a href="../../posts/linux/bash_profile.html"><strong aria-hidden="true">1.2.</strong> bash profile</a></li><li class="chapter-item "><a href="../../posts/linux/command_list.html"><strong aria-hidden="true">1.3.</strong> command list</a></li><li class="chapter-item "><a href="../../posts/linux/git_guide.html"><strong aria-hidden="true">1.4.</strong> git guide</a></li><li class="chapter-item "><a href="../../posts/linux/tar.html"><strong aria-hidden="true">1.5.</strong> tar</a></li><li class="chapter-item "><a href="../../posts/Linux/git_cheatsheet.html"><strong aria-hidden="true">1.6.</strong> Git Cheatsheet</a></li><li class="chapter-item "><a href="../../posts/Linux/bash_cheatsheet.html"><strong aria-hidden="true">1.7.</strong> Bash Cheatsheet</a></li></ol></li><li class="chapter-item "><a href="../../posts/macos/mac.html"><strong aria-hidden="true">2.</strong> MacOS</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/macos/macos_profiles.html"><strong aria-hidden="true">2.1.</strong> macos profiles</a></li><li class="chapter-item "><a href="../../posts/macos/macos_pwn_env_setup.html"><strong aria-hidden="true">2.2.</strong> macos pwn env setup</a></li></ol></li><li class="chapter-item "><a href="../../posts/swift/swift.html"><strong aria-hidden="true">3.</strong> Swift</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/swift/learn_swift.html"><strong aria-hidden="true">3.1.</strong> learn swift basics</a></li><li class="chapter-item "><a href="../../posts/swift/swift_extensions.html"><strong aria-hidden="true">3.2.</strong> Swift extensions</a></li><li class="chapter-item "><a href="../../posts/swift/swiftui_extension.html"><strong aria-hidden="true">3.3.</strong> SwiftUI extensions</a></li><li class="chapter-item "><a href="../../posts/swift/install_swift.html"><strong aria-hidden="true">3.4.</strong> install swift</a></li><li class="chapter-item "><a href="../../posts/swift/task_planner.html"><strong aria-hidden="true">3.5.</strong> implment task panner app with SwiftUI</a></li><li class="chapter-item "><a href="../../posts/swift/swift_cheat_sheet.html"><strong aria-hidden="true">3.6.</strong> Swift Cheat Sheet</a></li><li class="chapter-item "><a href="../../posts/swift/yinci_url.html"><strong aria-hidden="true">3.7.</strong> Personal privacy protocol</a></li><li class="chapter-item "><a href="../../posts/swift/swift_regular_exressions.html"><strong aria-hidden="true">3.8.</strong> Swift regular exressions</a></li><li class="chapter-item "><a href="../../posts/ios/how_to_create_beautiful_ios_charts_in_swift.html"><strong aria-hidden="true">3.9.</strong> How to Create Beautiful iOS Charts in Swift</a></li><li class="chapter-item "><a href="../../posts/swift/swiftui_source_code.html"><strong aria-hidden="true">3.10.</strong> SwiftUI source code</a></li><li class="chapter-item "><a href="../../posts/swift/use_swift_fetch_iciba_api.html"><strong aria-hidden="true">3.11.</strong> use swift fetch iciba API</a></li></ol></li><li class="chapter-item "><a href="../../posts/ios/ios.html"><strong aria-hidden="true">4.</strong> iOS</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/ios/cocaposd_setup_and_install_for_ios_project.html"><strong aria-hidden="true">4.1.</strong> cocaposd setup and install for ios project</a></li><li class="chapter-item "><a href="../../posts/ios/swiftui_show_gif_image.html"><strong aria-hidden="true">4.2.</strong> SwiftUI show gif image</a></li><li class="chapter-item "><a href="../../posts/ios/implement_task_planner_app.html"><strong aria-hidden="true">4.3.</strong> implement Task planner App</a></li></ol></li><li class="chapter-item "><a href="../../posts/objective_c/objective_c.html"><strong aria-hidden="true">5.</strong> Objective-C</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/objective_c/objective_c_cheat_sheet.html"><strong aria-hidden="true">5.1.</strong> Objective-C Cheat Sheet</a></li><li class="chapter-item "><a href="../../posts/objective_c/objective_c_for_absolute_beginners_read_note.html"><strong aria-hidden="true">5.2.</strong> Objective-C Note</a></li></ol></li><li class="chapter-item "><a href="../../posts/dart/dart.html"><strong aria-hidden="true">6.</strong> Dart</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/dart/flutter.html"><strong aria-hidden="true">6.1.</strong> Flutter Cheat Sheet</a></li><li class="chapter-item "><a href="../../posts/dart/dart_cheat_sheet.html"><strong aria-hidden="true">6.2.</strong> Dart Cheat Sheet</a></li><li class="chapter-item "><a href="../../posts/flutter/flutter_dev_test.html"><strong aria-hidden="true">6.3.</strong> Flutter dev test</a></li></ol></li><li class="chapter-item "><a href="../../posts/rust/rust.html"><strong aria-hidden="true">7.</strong> Rust</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/rust/offline_use_rust.html"><strong aria-hidden="true">7.1.</strong> Offline use rust</a></li><li class="chapter-item "><a href="../../posts/rust/rust_grammer.html"><strong aria-hidden="true">7.2.</strong> rust grammar</a></li><li class="chapter-item "><a href="../../posts/rust/pase_string_and_decimal_conversion.html"><strong aria-hidden="true">7.3.</strong> pase string and decimal conversion</a></li><li class="chapter-item "><a href="../../posts/rust/parse_types.html"><strong aria-hidden="true">7.4.</strong> rust types</a></li><li class="chapter-item "><a href="../../posts/rust/rust_life_cycle.html"><strong aria-hidden="true">7.5.</strong> Rust life cycle</a></li><li class="chapter-item "><a href="../../posts/rust/rust_generic.html"><strong aria-hidden="true">7.6.</strong> rust generics</a></li><li class="chapter-item "><a href="../../posts/rust/rust_implment_matrix.html"><strong aria-hidden="true">7.7.</strong> Rust implement matrix</a></li><li class="chapter-item "><a href="../../posts/rust/rust_sort.html"><strong aria-hidden="true">7.8.</strong> Rust implement sort algorithms</a></li><li class="chapter-item "><a href="../../posts/rust/implement_aes_encryption.html"><strong aria-hidden="true">7.9.</strong> Rust implement AEC encryption and decryption</a></li><li class="chapter-item "><a href="../../posts/rust/implement_trie_data_structure.html"><strong aria-hidden="true">7.10.</strong> implement trie data structure</a></li><li class="chapter-item "><a href="../../posts/rust/rust_implement_tree.html"><strong aria-hidden="true">7.11.</strong> implement tree data_structure</a></li><li class="chapter-item "><a href="../../posts/rust/list_dir.html"><strong aria-hidden="true">7.12.</strong> list dir</a></li><li class="chapter-item "><a href="../../posts/rust/fast_way_to_implment_object_trait.html"><strong aria-hidden="true">7.13.</strong> fast way to implment object trait</a></li><li class="chapter-item "><a href="../../posts/rust/compress_rust_binary_size.html"><strong aria-hidden="true">7.14.</strong> compress rust binary size</a></li><li class="chapter-item "><a href="../../posts/rust/implment_file_upload_backend.html"><strong aria-hidden="true">7.15.</strong> impliment file upload</a></li><li class="chapter-item "><a href="../../posts/rust/this_is_add_post_cli_implementation_in_rust.html"><strong aria-hidden="true">7.16.</strong> this is add_post cli implementation in rust</a></li><li class="chapter-item "><a href="../../posts/rust/use_rust_implment_a_copyclipbord_cli.html"><strong aria-hidden="true">7.17.</strong> Use rust implment a copyclipbord CLI</a></li><li class="chapter-item "><a href="../../posts/rust/sqlite_database_add_delete_update_show_in_rust.html"><strong aria-hidden="true">7.18.</strong> sqlite database add delete update show in rust</a></li><li class="chapter-item "><a href="../../posts/rust/implementing_tokio_joinhandle_for_wasm.html"><strong aria-hidden="true">7.19.</strong> Implementing tokio JoinHandle for wasm</a></li><li class="chapter-item "><a href="../../posts/rust/rust_implement_a_crate_for_encode_and_decode_brainfuck_and_ook.html"><strong aria-hidden="true">7.20.</strong> rust implement a crate for encode and decode brainfuck and ook</a></li><li class="chapter-item "><a href="../../posts/rust/slint_builtin_elements.html"><strong aria-hidden="true">7.21.</strong> Slint Builtin Elements</a></li><li class="chapter-item "><a href="../../posts/rust/corporate_network_install_rust_on_windows.html"><strong aria-hidden="true">7.22.</strong> Corporate network install Rust on windows</a></li><li class="chapter-item "><a href="../../posts/rust/rust_binary_file_how_to_judge_static_link_or_dynamic_link_in_macos.html"><strong aria-hidden="true">7.23.</strong> rust binary file how to judge static link or dynamic link in Macos</a></li><li class="chapter-item "><a href="../../posts/rust/rust_binary_include_dir_and_get_contents.html"><strong aria-hidden="true">7.24.</strong> rust binary include dir and get contents</a></li><li class="chapter-item "><a href="../../posts/rust/how_to_create_yolov8_based_object_detection_web_service_using_python,_julia,_node.js,_javascript,_go_and_rust.html"><strong aria-hidden="true">7.25.</strong> How to create YOLOv8-based object detection web service using Python, Julia, Node.js, JavaScript, Go and Rust</a></li><li class="chapter-item "><a href="../../posts/rust/implment_builder_proc_macro_for_command_struct.html"><strong aria-hidden="true">7.26.</strong> implment Builder proc-macro for Command struct</a></li></ol></li><li class="chapter-item "><a href="../../posts/java/java.html"><strong aria-hidden="true">8.</strong> Java</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/java/java_grammar.html"><strong aria-hidden="true">8.1.</strong> java grammar and codewar</a></li><li class="chapter-item "><a href="../../posts/java/run_jar.html"><strong aria-hidden="true">8.2.</strong> java run .jar</a></li><li class="chapter-item "><a href="../../posts/java/java_pomxml_add_defaultgoal_to_build.html"><strong aria-hidden="true">8.3.</strong> Java pomxml add defaultGoal to build</a></li><li class="chapter-item "><a href="../../posts/java/java_set_mvn_mirror.html"><strong aria-hidden="true">8.4.</strong> Java set mvn mirror</a></li></ol></li><li class="chapter-item "><a href="../../posts/python/python.html"><strong aria-hidden="true">9.</strong> Python</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/python/convert_pesn.html"><strong aria-hidden="true">9.1.</strong> convert pesn</a></li><li class="chapter-item "><a href="../../posts/python/find_remove_dir.html"><strong aria-hidden="true">9.2.</strong> find and remove dir</a></li><li class="chapter-item "><a href="../../posts/python/timing_message.html"><strong aria-hidden="true">9.3.</strong> wechat send message</a></li><li class="chapter-item "><a href="../../posts/python/use_python_openpyxl_package_read_and_edit_excel_files.html"><strong aria-hidden="true">9.4.</strong> Use python openpyxl package read and edit excel files</a></li><li class="chapter-item "><a href="../../posts/python/sanctum_model_yaml.html"><strong aria-hidden="true">9.5.</strong> sanctum model yaml</a></li><li class="chapter-item "><a href="../../posts/python/how_to_detect_objects_on_images_using_the_yolov8_neural_network.html"><strong aria-hidden="true">9.6.</strong> How to detect objects on images using the YOLOv8 neural network</a></li><li class="chapter-item "><a href="../../posts/python/use_huggingface_model.html"><strong aria-hidden="true">9.7.</strong> use huggingface model</a></li></ol></li><li class="chapter-item "><a href="../../posts/go/go.html"><strong aria-hidden="true">10.</strong> Go</a></li><li class="chapter-item "><a href="../../posts/javascript/js.html"><strong aria-hidden="true">11.</strong> Javascript</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/javascript/js_tutorial.html"><strong aria-hidden="true">11.1.</strong> js tutorial</a></li><li class="chapter-item "><a href="../../posts/javascript/js_tutorial_map.html"><strong aria-hidden="true">11.2.</strong> ja map</a></li><li class="chapter-item "><a href="../../posts/javascript/js_tutorial_math.html"><strong aria-hidden="true">11.3.</strong> js math</a></li><li class="chapter-item "><a href="../../posts/javascript/js_tutorial_object.html"><strong aria-hidden="true">11.4.</strong> js object</a></li><li class="chapter-item "><a href="../../posts/javascript/js_tutorial_set.html"><strong aria-hidden="true">11.5.</strong> js set</a></li><li class="chapter-item "><a href="../../posts/javascript/single_thread_and_asynchronous.html"><strong aria-hidden="true">11.6.</strong> single thread and asynchronous</a></li><li class="chapter-item "><a href="../../posts/javascript/this.html"><strong aria-hidden="true">11.7.</strong> js this</a></li><li class="chapter-item "><a href="../../posts/javascript/js_implment_aes.html"><strong aria-hidden="true">11.8.</strong> js implment aes</a></li><li class="chapter-item "><a href="../../posts/javascript/getting_started_with_ajax.html"><strong aria-hidden="true">11.9.</strong> getting started with ajax</a></li><li class="chapter-item "><a href="../../posts/javascript/BinarySearchTree.html"><strong aria-hidden="true">11.10.</strong> binary search tree</a></li><li class="chapter-item "><a href="../../posts/javascript/goole_zx.html"><strong aria-hidden="true">11.11.</strong> goole zx</a></li><li class="chapter-item "><a href="../../posts/javascript/es6.html"><strong aria-hidden="true">11.12.</strong> es6</a></li></ol></li><li class="chapter-item "><a href="../../posts/ruby/ruby.html"><strong aria-hidden="true">12.</strong> Ruby</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/ruby/rails_setup_env.html"><strong aria-hidden="true">12.1.</strong> ruby on rails setup environment</a></li><li class="chapter-item "><a href="../../posts/ruby/learn_ruby.html"><strong aria-hidden="true">12.2.</strong> learn ruby</a></li><li class="chapter-item "><a href="../../posts/ruby/ruby_note.html"><strong aria-hidden="true">12.3.</strong> Ruby Note</a></li><li class="chapter-item "><a href="../../posts/ruby/setup_ruby_for_ctf.html"><strong aria-hidden="true">12.4.</strong> Setup ruby for CTF</a></li></ol></li><li class="chapter-item "><a href="../../posts/react/react.html"><strong aria-hidden="true">13.</strong> React</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/react/react_life_cycle.html"><strong aria-hidden="true">13.1.</strong> react life cycle</a></li><li class="chapter-item "><a href="../../posts/react/react_router.html"><strong aria-hidden="true">13.2.</strong> react router</a></li><li class="chapter-item "><a href="../../posts/react/react_this.html"><strong aria-hidden="true">13.3.</strong> react this</a></li><li class="chapter-item "><a href="../../posts/react/react_interviw.html"><strong aria-hidden="true">13.4.</strong> react interview</a></li><li class="chapter-item "><a href="../../posts/react/important_react_interview.html"><strong aria-hidden="true">13.5.</strong> important react interview</a></li><li class="chapter-item "><a href="../../posts/react/react_quick_reference.html"><strong aria-hidden="true">13.6.</strong> react quick reference</a></li><li class="chapter-item "><a href="../../posts/react/redux_quick_reference.html"><strong aria-hidden="true">13.7.</strong> redux quick reference</a></li></ol></li><li class="chapter-item "><a href="../../posts/vue/vue.html"><strong aria-hidden="true">14.</strong> Vue</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/vue/vue_ajax.html"><strong aria-hidden="true">14.1.</strong> vue ajax</a></li></ol></li><li class="chapter-item "><a href="../../posts/angular/angular.html"><strong aria-hidden="true">15.</strong> Angular</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/angular/controller_communication.html"><strong aria-hidden="true">15.1.</strong> controller communication</a></li><li class="chapter-item "><a href="../../posts/angular/creating_custom_directives.html"><strong aria-hidden="true">15.2.</strong> creating custom directives</a></li><li class="chapter-item "><a href="../../posts/angular/directive_notes.html"><strong aria-hidden="true">15.3.</strong> directive notes</a></li><li class="chapter-item "><a href="../../posts/angular/directive_communication.html"><strong aria-hidden="true">15.4.</strong> directive communication</a></li><li class="chapter-item "><a href="../../posts/angular/post_params.html"><strong aria-hidden="true">15.5.</strong> post params</a></li><li class="chapter-item "><a href="../../posts/angular/read_json_angular.html"><strong aria-hidden="true">15.6.</strong> read json angular</a></li><li class="chapter-item "><a href="../../posts/angular/same_route_reload.html"><strong aria-hidden="true">15.7.</strong> same route reload</a></li></ol></li><li class="chapter-item "><a href="../../posts/css/css.html"><strong aria-hidden="true">16.</strong> Css</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/css/use_css_media.html"><strong aria-hidden="true">16.1.</strong> use css media</a></li></ol></li><li class="chapter-item "><a href="../../posts/php/php.html"><strong aria-hidden="true">17.</strong> Php</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/php/for_php_string_implment_some_extemtion_functions.html"><strong aria-hidden="true">17.1.</strong> for php string implment some extemtion functions</a></li><li class="chapter-item "><a href="../../posts/php/php_cheatsheet.html"><strong aria-hidden="true">17.2.</strong> PHP cheatsheet</a></li></ol></li><li class="chapter-item "><a href="../../posts/windows/windows.html"><strong aria-hidden="true">18.</strong> Windows</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/windows/windows.html"><strong aria-hidden="true">18.1.</strong> Windows</a></li><li class="chapter-item "><a href="../../posts/windows/windows10_use_powershell_dedup_redundent_path.html"><strong aria-hidden="true">18.2.</strong> Windows10 use PowerShell dedup redundent PATH</a></li></ol></li><li class="chapter-item "><a href="../../posts/leetcode/leetcode.html"><strong aria-hidden="true">19.</strong> Leetcode</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/leetcode/rust_leetcode.html"><strong aria-hidden="true">19.1.</strong> rust leetcode</a></li><li class="chapter-item "><a href="../../posts/leetcode/rust_codewar.html"><strong aria-hidden="true">19.2.</strong> rust codewar</a></li><li class="chapter-item "><a href="../../posts/leetcode/swift_codewar.html"><strong aria-hidden="true">19.3.</strong> swift codewar</a></li><li class="chapter-item "><a href="../../posts/leetcode/js_leetcode.html"><strong aria-hidden="true">19.4.</strong> js leetcode</a></li><li class="chapter-item "><a href="../../posts/leetcode/java_leetcode.html"><strong aria-hidden="true">19.5.</strong> java leetcode</a></li><li class="chapter-item "><a href="../../posts/leetcode/rust_huawei.html"><strong aria-hidden="true">19.6.</strong> huawei test</a></li><li class="chapter-item "><a href="../../posts/leetcode/rust_utils.html"><strong aria-hidden="true">19.7.</strong> rust common functions</a></li><li class="chapter-item "><a href="../../posts/leetcode/olympiad_training.html"><strong aria-hidden="true">19.8.</strong> Computer olympiad training</a></li></ol></li><li class="chapter-item expanded "><a href="../../posts/ctf/CTF.html"><strong aria-hidden="true">20.</strong> CTF</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/ctf/CTF_Note.html"><strong aria-hidden="true">20.1.</strong> CTF Note</a></li><li class="chapter-item "><a href="../../posts/ctf/0.1_Web.html"><strong aria-hidden="true">20.2.</strong> Web</a></li><li class="chapter-item "><a href="../../posts/ctf/4.1_Misc.html"><strong aria-hidden="true">20.3.</strong> Misc</a></li><li class="chapter-item "><a href="../../posts/ctf/3.2_PWN_note.html"><strong aria-hidden="true">20.4.</strong> PWN</a></li><li class="chapter-item "><a href="../../posts/ctf/3.1_Crypto.html"><strong aria-hidden="true">20.5.</strong> Crypto</a></li><li class="chapter-item expanded "><a href="../../posts/ctf/3.4_RSA_note.html" class="active"><strong aria-hidden="true">20.6.</strong> Rsa attack</a></li><li class="chapter-item "><a href="../../posts/ctf/3.5_Base64.html"><strong aria-hidden="true">20.7.</strong> Base64</a></li><li class="chapter-item "><a href="../../posts/ctf/0.0_SQL Injection Cheatsheet.html"><strong aria-hidden="true">20.8.</strong> SQL Injection Cheatsheet</a></li><li class="chapter-item "><a href="../../posts/ctf/1.1_SQL_injection.html"><strong aria-hidden="true">20.9.</strong> SQL Injection</a></li><li class="chapter-item "><a href="../../posts/ctf/1.2_SQL_injection_UNION_attacks.html"><strong aria-hidden="true">20.10.</strong> SQL Injection UNION attacks</a></li><li class="chapter-item "><a href="../../posts/ctf/1.3_Blind SQL injection.html"><strong aria-hidden="true">20.11.</strong> Blind SQL Injection</a></li><li class="chapter-item "><a href="../../posts/ctf/1.4_Code Injection.html"><strong aria-hidden="true">20.12.</strong> Code Injection</a></li><li class="chapter-item "><a href="../../posts/ctf/1.5_SSRF.html"><strong aria-hidden="true">20.13.</strong> SSRF</a></li><li class="chapter-item "><a href="../../posts/ctf/1.6_OS command injection.html"><strong aria-hidden="true">20.14.</strong> OS command injection</a></li><li class="chapter-item "><a href="../../posts/ctf/1.7_Local file inclusion.html"><strong aria-hidden="true">20.15.</strong> Local file inclusion</a></li><li class="chapter-item "><a href="../../posts/ctf/1.8_Remote file inclusion.html"><strong aria-hidden="true">20.16.</strong> Remote file inclusion</a></li><li class="chapter-item "><a href="../../posts/ctf/1.9_CSRFm.html"><strong aria-hidden="true">20.17.</strong> CSRF</a></li><li class="chapter-item "><a href="../../posts/ctf/1.10_NoSQL injection.html"><strong aria-hidden="true">20.18.</strong> NoSQL injection</a></li><li class="chapter-item "><a href="../../posts/ctf/1.11_JSON injection.html"><strong aria-hidden="true">20.19.</strong> JSON injection</a></li><li class="chapter-item "><a href="../../posts/ctf/1.12_CTF_Web_SQL_Note.html"><strong aria-hidden="true">20.20.</strong> CTF Web SQL Note</a></li><li class="chapter-item "><a href="../../posts/ctf/2.1_XXE.html"><strong aria-hidden="true">20.21.</strong> XXE</a></li><li class="chapter-item "><a href="../../posts/ctf/2.2_XSS.html"><strong aria-hidden="true">20.22.</strong> XSS</a></li><li class="chapter-item "><a href="../../posts/ctf/2.3_Upload File.html"><strong aria-hidden="true">20.23.</strong> Upload File</a></li><li class="chapter-item "><a href="../../posts/ctf/2.4_serialize_unserialize.html"><strong aria-hidden="true">20.24.</strong> serialize unserialize</a></li><li class="chapter-item "><a href="../../posts/ctf/2.5_Race condition.html"><strong aria-hidden="true">20.25.</strong> Race condition</a></li><li class="chapter-item "><a href="../../posts/ctf/zip_plain_text_attack.html"><strong aria-hidden="true">20.26.</strong> Zip plain text attack</a></li><li class="chapter-item "><a href="../../posts/ctf/3.3_pwn HCTF2016 brop.html"><strong aria-hidden="true">20.27.</strong> pwn HCTF2016 brop</a></li><li class="chapter-item "><a href="../../posts/ctf/pwn_patch_defense_skill.html"><strong aria-hidden="true">20.28.</strong> PWN Patch defense skill</a></li><li class="chapter-item "><a href="../../posts/ctf/pwn_stack_overflow.html"><strong aria-hidden="true">20.29.</strong> PWN stack overflow</a></li><li class="chapter-item "><a href="../../posts/ctf/pwn_heap_overflow.html"><strong aria-hidden="true">20.30.</strong> PWN heap overflow</a></li><li class="chapter-item "><a href="../../posts/ctf/pwn_format_string_vulnerability.html"><strong aria-hidden="true">20.31.</strong> PWN Format String Vulnerability</a></li><li class="chapter-item "><a href="../../posts/ctf/kali_linux_tutorials.html"><strong aria-hidden="true">20.32.</strong> Kali linux tutorials</a></li><li class="chapter-item "><a href="../../posts/ctf/google_dorks_2023_lists.html"><strong aria-hidden="true">20.33.</strong> Google Dorks 2023 Lists</a></li><li class="chapter-item "><a href="../../posts/ctf/dvwa_writeup.html"><strong aria-hidden="true">20.34.</strong> DVWA WriteUp</a></li><li class="chapter-item "><a href="../../posts/ctf/bwapp_writeup.html"><strong aria-hidden="true">20.35.</strong> bWAPP WriteUp</a></li><li class="chapter-item "><a href="../../posts/ctf/sqlilabs_writeup.html"><strong aria-hidden="true">20.36.</strong> sqlilabs WriteUp</a></li><li class="chapter-item "><a href="../../posts/ctf/pwnable_kr_challenge.html"><strong aria-hidden="true">20.37.</strong> Solutions for pwnable.kr</a></li><li class="chapter-item "><a href="../../posts/ctf/the_periodic_table.html"><strong aria-hidden="true">20.38.</strong> The Periodic Table</a></li><li class="chapter-item "><a href="../../posts/ctf/pwntools_cheatsheet.html"><strong aria-hidden="true">20.39.</strong> Pwntools Cheatsheet</a></li><li class="chapter-item "><a href="../../posts/ctf/gdb_cheatsheet.html"><strong aria-hidden="true">20.40.</strong> GDB Cheatsheet</a></li></ol></li><li class="chapter-item "><a href="../../posts/iltes/iltes.html"><strong aria-hidden="true">21.</strong> ILTES</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/iltes/iltes_writing.html"><strong aria-hidden="true">21.1.</strong> ILTES Writing</a></li></ol></li></ol>
            </div>
            <div id="sidebar-resize-handle" class="sidebar-resize-handle"></div>
        </nav>

        <!-- Track and set sidebar scroll position -->
        <script>
            var sidebarScrollbox = document.querySelector('#sidebar .sidebar-scrollbox');
            sidebarScrollbox.addEventListener('click', function(e) {
                if (e.target.tagName === 'A') {
                    sessionStorage.setItem('sidebar-scroll', sidebarScrollbox.scrollTop);
                }
            }, { passive: true });
            var sidebarScrollTop = sessionStorage.getItem('sidebar-scroll');
            sessionStorage.removeItem('sidebar-scroll');
            if (sidebarScrollTop) {
                // preserve sidebar scroll position when navigating via links within sidebar
                sidebarScrollbox.scrollTop = sidebarScrollTop;
            } else {
                // scroll sidebar to current active section when navigating via "next/previous chapter" buttons
                var activeSection = document.querySelector('#sidebar .active');
                if (activeSection) {
                    activeSection.scrollIntoView({ block: 'center' });
                }
            }
        </script>

        <div id="page-wrapper" class="page-wrapper">

            <div class="page">
                                <div id="menu-bar-hover-placeholder"></div>
                <div id="menu-bar" class="menu-bar sticky">
                    <div class="left-buttons">
                        <button id="sidebar-toggle" class="icon-button" type="button" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
                            <i class="fa fa-bars"></i>
                        </button>
                        <button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
                            <i class="fa fa-paint-brush"></i>
                        </button>
                        <ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
                            <li role="none"><button role="menuitem" class="theme" id="light">Light</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
                        </ul>
                        <button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
                            <i class="fa fa-search"></i>
                        </button>
                    </div>

                    <h1 class="menu-title">Andrew&#x27;s Blog</h1>

                    <div class="right-buttons">
                        <a href="https://gitee.com/dnrops/dnrops" title="Git repository" aria-label="Git repository">
                            <i id="git-repository-button" class="fa fa-github"></i>
                        </a>

                    </div>
                </div>

                <div id="search-wrapper" class="hidden">
                    <form id="searchbar-outer" class="searchbar-outer">
                        <input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
                    </form>
                    <div id="searchresults-outer" class="searchresults-outer hidden">
                        <div id="searchresults-header" class="searchresults-header"></div>
                        <ul id="searchresults">
                        </ul>
                    </div>
                </div>

                <!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
                <script>
                    document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
                    document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
                    Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
                        link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
                    });
                </script>

                <div id="content" class="content">
                    <main>
                        <h1 id="ctf中的rsa及攻击方法笔记"><a class="header" href="#ctf中的rsa及攻击方法笔记">CTF中的RSA及攻击方法笔记</a></h1>
<h2 id="数论"><a class="header" href="#数论">数论</a></h2>
<h3 id="模运算规则"><a class="header" href="#模运算规则">模运算规则:</a></h3>
<p>模运算与基本四则运算有些相似，但是除法例外。其规则如下:</p>
<p>(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
(a ^ b) % p = ((a % p)^b) % p</p>
<p>结合律：</p>
<p>((a+b) % p + c) % p = (a + (b+c) % p) % p
((a*b) % p * c)% p = (a <em>(b</em>c)%p) % p</p>
<p>交换律：</p>
<p>(a + b) % p = (b + a) % p
(a * b) % p = (b * a) % p</p>
<p>分配律：</p>
<p>((a +b)% p * c) % p = ((a * c) %p + (b * c) % p) % p</p>
<p>重要定理：</p>
<p>若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)
若a≡b (% p)，则对于任意的正整数c，都有(a * c) ≡ (b * c) (%p)
若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)，
(a * c) ≡ (b * d) (%p)</p>
<h3 id="最大公因子"><a class="header" href="#最大公因子">最大公因子</a></h3>
<p>两个数互素是指：除了它们除了1​外没有共同的因子。如果a和n的最大公因子等于1，那么可写作</p>
<p>$gcd(a,n)=1$</p>
<h4 id="欧几里得算法"><a class="header" href="#欧几里得算法">欧几里得算法</a></h4>
<p>又称碾转相除法，我们通常使用该方法计算最大公因子。</p>
<h4 id="欧几里得扩展算法"><a class="header" href="#欧几里得扩展算法">欧几里得扩展算法</a></h4>
<p>如果gcd(a, b) = c，则存在x, y，使得c = ax + by。</p>
<h3 id="同余"><a class="header" href="#同余">同余</a></h3>
<p>两个整数a、b，若它们除以整数m所得的余数相等，则称a与b对于模m同余或a同余于b模m。 记作：a≡b (mod m)， 读作：a同余于b模m，或读作a与b对模m同余，例如26≡2(mod 12)。</p>
<h4 id="模的逆元"><a class="header" href="#模的逆元">模的逆元</a></h4>
<p>简单来说，求a的逆，就是找一个 $x$，使得$1 = (a*x){\pmod n}$</p>
<p>也可记作 $a^{-1} \equiv x{\pmod {n}}$</p>
<h3 id="费马小定理和欧拉定理"><a class="header" href="#费马小定理和欧拉定理">费马小定理和欧拉定理</a></h3>
<p><strong>费马小定理</strong>是数论中的一个定理：假如 ${a}$ 是一个整数，${p}$ 是一个质数，那么${a^{p}-a}$是 $p$ 的倍数，可以表示为 $$a^{p}\equiv a{\pmod {p}}$$ 如果a不是p的倍数，这个定理也可以写成 $$a^{{p-1}}\equiv 1{\pmod {p}}$$ <strong>欧拉定理</strong>若$n,a$为正整数，且$n,a$互素（即$gcd(a,n)=1$），那么 $$a^{{\varphi (n)}}\equiv 1{\pmod n}$$</p>
<p>因为欧拉定理是费马小定理的推广，所以欧拉定理的条件对任意互素的a和n与费马小定理的条件若p是素数，a是正整数且不能被p整除相比不可能是缩小范围。</p>
<p>可参考：https://www.cnblogs.com/nysanier/archive/2011/04/12/2014000.html</p>
<h3 id="中国剩余定理"><a class="header" href="#中国剩余定理">中国剩余定理</a></h3>
<p>可参考：https://blog.csdn.net/u010468553/article/details/38346195/</p>
<h2 id="rsa原理基础题目"><a class="header" href="#rsa原理基础题目">RSA原理+基础题目</a></h2>
<p>参考1：https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_theory-zh/ 参考2：https://bbs.pediy.com/thread-263069.htm 基于大整数因数分解难题。</p>
<h1 id="rsa"><a class="header" href="#rsa">RSA</a></h1>
<h3 id="rsa简介"><a class="header" href="#rsa简介">RSA简介</a></h3>
<p>倘若在加解密信息的过程中，能让加密密钥（公钥）与解密密钥（私钥）不同，即</p>
<pre><code>1. 甲要传密信给乙，乙先根据某种算法得出本次与甲通信的公钥与私钥；
2. 乙将公钥传给甲（公钥可以让任何人知道，即使泄露也没有任何关系）；
3. 甲使用乙传给的公钥加密要发送的信息原文m，发送给乙密文c；
4. 乙使用自己的私钥解密密文c，得到信息原文m .
</code></pre>
<h3 id="数学概念"><a class="header" href="#数学概念">数学概念</a></h3>
<p>需要了解的几个数学概念</p>
<p>1.质数与互质数
2.欧拉函数
3.欧拉定理
4.模反元素
5.同余</p>
<h3 id="质数与互质数"><a class="header" href="#质数与互质数">质数与互质数</a></h3>
<p>一个大于1的自然数，除了1和它本身外，不能被其他自然数整除（除0以外）的数称之为质数（素数）；否则称为合数。</p>
<p>公约数只有1的两个数，叫做互质数。</p>
<p>1.任意两个质数一定构成互质数（如3与11、53与61）；
2.大数是质数的两个数一定是互质数（如97与88）；</p>
<p>在RSA算法中，我们通常使用以上第1条与第2条，即选取两个本身都是质数的数作为互质数</p>
<h3 id="欧拉函数"><a class="header" href="#欧拉函数">欧拉函数</a></h3>
<p>任意给定正整数n，计算在小于等于n的正整数之中，有多少个与n构成互质关系？
计算这个值的方法就叫做欧拉函数，以φ(n)表示.</p>
<p>例如，在1到8之中，与8形成互质关系的是1、3、5、7，所以φ(n)=4</p>
<p>在RSA算法中，我们需要明白欧拉函数对以下定理成立</p>
<p>1.如果n可以分解成两个互质的整数之积，即n=p×q，则有：φ(n)=φ(pq)=φ(p)φ(q);
2.根据“大数是质数的两个数一定是互质数”可以知道：
一个数如果是质数，则小于它的所有正整数与它都是互质数；
所以如果一个数p是质数，则有：φ(p)=p-1</p>
<p>由上易得，若我们知道一个数n可以分解为两个质数p和q的乘积，则有</p>
<p>φ(n)=(p-1)(q-1)</p>
<h3 id="欧拉定理"><a class="header" href="#欧拉定理">欧拉定理</a></h3>
<p>如果两个正整数a和n互质，则n的欧拉函数φ(n)可以让下面的等式成立：
aφ(n)≡1(modn)</p>
<h3 id="模运算与模反元素"><a class="header" href="#模运算与模反元素">模运算与模反元素</a></h3>
<p>模运算：让m去被n整除，只取所得的余数作为结果，就叫做模运算。
例如，10 mod 3 = 1 、26 mod 6 = 2 、28 mod 2 = 0</p>
<p>模反元素：如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1
ab≡1( mod n)
这时候，b就是a的模反元素</p>
<h3 id="同余-1"><a class="header" href="#同余-1">同余</a></h3>
<p>“≡”是数论中表示同余的符号，定义如下：</p>
<p>给定一个正整数m，如果两个整数a和b满足a-b能被m整除，即(a-b) mod m=0，
那么就称整数a与b对模m同余，记作a≡b(modm)，同时可成立a mod m=b</p>
<h3 id="需要记住的参数"><a class="header" href="#需要记住的参数">需要记住的参数</a></h3>
<p>p,q:大整数N的两个因子（factor）
N:大整数N，我们称之为模数（modulus）
e,d:互为模反数的两个指数（exponent）
c,m:密文和明文，这里一般指的是一个十进制的数
e：公钥
d：私钥</p>
<h3 id="rsa加密流程"><a class="header" href="#rsa加密流程">RSA加密流程</a></h3>
<ul>
<li>
<p>首先选择两个互为质数p和q (q与p互素，公因数只有1)</p>
</li>
<li>
<p>求出n = p * q</p>
</li>
<li>
<p>φ(n) = (p−1)*(q−1) 欧拉公式</p>
</li>
<li>
<p>公钥 e : 随机取，要求：e 和 φ(n) 互素（公因数只有 1）; 1&lt; e &lt; φ(n)；</p>
</li>
<li>
<p>私钥 d ：ed  ≡  1 （mod  φ(n) ）   （ed 除以 φ(n) 的 余数 为  1 ）</p>
</li>
<li>
<p>e与d互为模反元素。</p>
</li>
<li>
<p>明文加密后的密文c = pow(m, e, n)</p>
</li>
</ul>
<p><img src="https://gitcode.net/dnrops/blog_images/-/raw/main/all_imgs/rsa1.png" alt="image" /></p>
<ul>
<li>密文解密后的明文m = pow(c, d, n)</li>
</ul>
<p><img src="https://gitcode.net/dnrops/blog_images/-/raw/main/all_imgs/rsa2.png" alt="image" /></p>
<pre><code>pow(x, y[, z])
函数是计算x的y次方，如果z在存在，则再对结果进行取模，其结果等效于pow(x,y) %z
</code></pre>
<h3 id="依赖库的安装"><a class="header" href="#依赖库的安装">依赖库的安装</a></h3>
<pre><code class="language-bash">apt-get install libgmp-dev
apt-get install libmpfr-dev
apt-get install libmpc-dev
apt-get install python3-pip
pip install gmpy2
</code></pre>
<h3 id="rsa题目"><a class="header" href="#rsa题目">RSA题目</a></h3>
<h4 id="简单"><a class="header" href="#简单">简单</a></h4>
<p>在一次RSA密钥对生成中，假设p=473398607161，q=4511491，e=17
求解出d作为flag提交</p>
<pre><code class="language-python">import gmpy2
p=473398607161
q=4511491
e=17
d=gmpy2.invert(e,(q-1)*(p-1))  # 求逆元，de ≡ 1 mod n
print(d)
</code></pre>
<h4 id="进阶"><a class="header" href="#进阶">进阶</a></h4>
<h2 id="rsarsa"><a class="header" href="#rsarsa">rsarsa</a></h2>
<p>Math is cool! Use the RSA algorithm to decode the secret message, c, p, q, and e are parameters for the RSA algorithm.</p>
<p>p =  9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q =  11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e =  65537
c =  83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034</p>
<p>Use RSA to find the secret message</p>
<pre><code class="language-python"># 已知 p q e c 求 m
import gmpy2
p =9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q =11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e =  65537
n = p*q
c =83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034


d = gmpy2.invert(e,(p-1)*(q-1)) # d是私钥
m = gmpy2.powmod(c,d,n)  # 幂取模，结果是 C = (M^e) mod n
# m = pow(c,d,n)
print(m)
</code></pre>
<h3 id="buuctf-rsa"><a class="header" href="#buuctf-rsa">BUUCTF-RSA</a></h3>
<p>题目描述：</p>
<p>在一次RSA密钥对生成中，假设p=473398607161，q=4511491，e=17，求解出d作为flag提交</p>
<p>解题：</p>
<pre><code>import gmpy2
p,q,e = 473398607161, 4511491, 17
phi = (p-1) * (q-1)
d = gmpy2.invert(e, phi)
print(d)
</code></pre>
<h3 id="buuctf-rsarsa"><a class="header" href="#buuctf-rsarsa">BUUCTF-rsarsa</a></h3>
<p>题目描述：</p>
<p>Math is cool! Use the RSA algorithm to decode the secret message, c, p, q, and e are parameters for the RSA algorithm.</p>
<p>p =  9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q =  11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e =  65537
c =  83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034</p>
<p>Use RSA to find the secret message</p>
<h2 id="rsa数论"><a class="header" href="#rsa数论">RSA+数论</a></h2>
<h3 id="2018-codegate-ctf-rsababy"><a class="header" href="#2018-codegate-ctf-rsababy">2018 CodeGate CTF Rsababy</a></h3>
<p>题目描述：</p>
<p>e = 65537
n = p * q
pi_n = (p-1)<em>(q-1)
d = mulinv(e, pi_n)
h = (d+p)^(d-p)
g = d</em>(p-0xdeadbeef)</p>
<p>解析参看：</p>
<p>https://github.com/ashutosh1206/Crypto-CTF-Writeups/tree/master/2018/Codegate-CTF-Preliminary/RSAbaby</p>
<p>解题：</p>
<pre><code>from Crypto.Util.number import *
# g,N,Encrypted_Data已知
e = 65537

# Using Euler's Theorem and Fermat's Little Theorem we have
t1 = pow(2, e*g, N)
t2 = pow(2, 0xdeadbeef, N)
p = GCD((t1*t2)-2,N)

assert N % p == 0
q = N / p
phin = (p-1)*(q-1)
d = inverse(e, phin)
m = pow(Encrypted_Data, d, N)
print long_to_bytes(m)
</code></pre>
<h2 id="模相关攻击"><a class="header" href="#模相关攻击">模相关攻击</a></h2>
<h3 id="暴力分解n"><a class="header" href="#暴力分解n">暴力分解N</a></h3>
<h4 id="可攻击特征"><a class="header" href="#可攻击特征">可攻击特征</a></h4>
<p>在 N 的比特位数小于 512 的时候，可以采用大整数分解的策略获取 p 和 q。</p>
<h4 id="攻击方法"><a class="header" href="#攻击方法">攻击方法</a></h4>
<p>大整数分解一般有以下两种方法：</p>
<ol>
<li>在线数据库查询：<a href="http://factordb.com/">http://factordb.com/</a></li>
<li>yafu工具</li>
</ol>
<h4 id="jarvisoj---easy-rsa"><a class="header" href="#jarvisoj---easy-rsa">JarvisOJ - Easy RSA</a></h4>
<p>题目描述：</p>
<p>还记得 veryeasy RSA 吗？是不是不难？那继续来看看这题吧，这题也不难。
已知一段 RSA 加密的信息为：0xdc2eeeb2782c 且已知加密所用的公钥：
N=322831561921859 e = 23
请解密出明文，提交时请将数字转化为 ascii 码提交
比如你解出的明文是 0x6162，那么请提交字符串 ab
提交格式：PCTF{明文字符串}</p>
<p>解题：</p>
<h1 id="经过-httpfactordbcom-查询得出1357488123781539"><a class="header" href="#经过-httpfactordbcom-查询得出1357488123781539">经过 http://factordb.com/ 查询得出：13574881,23781539</a></h1>
<pre><code>from Crypto.Util.number import long_to_bytes
import gmpy2

p,q = 13574881,23781539
n = q*p
e = 23
c = 0xdc2eeeb2782c
phi = (q-1) * (p-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)
m = long_to_bytes(m)
print(m)
</code></pre>
<h3 id="多因子"><a class="header" href="#多因子">多因子</a></h3>
<h4 id="可攻击特征-1"><a class="header" href="#可攻击特征-1">可攻击特征</a></h4>
<p>N可被分解为多个素数</p>
<h4 id="原理"><a class="header" href="#原理">原理</a></h4>
<p>如果选取两个以上的素数，记为 $p1,p2,p3…$，它们相乘得到 nn，那么：</p>
<p>$φ(n)=(p1−1)(p2−1)(p3−1)$</p>
<p>公钥、私钥、加解密都与一般 RSA 相同。</p>
<p>选取多因子，虽然会减少生成密钥的时间，但同样也更容易被破解。</p>
<h4 id="2018-picoctfsuper-safe-rsa-3"><a class="header" href="#2018-picoctfsuper-safe-rsa-3">2018 picoctf：Super Safe RSA 3</a></h4>
<p><strong>题目</strong></p>
<p>每次<code>nc</code>连接可以获得不同的 cc、nn、ee。</p>
<p>例如一次连接中：</p>
<p>c: 236434294562852381842307785543347919217676481857496426677823656807506421759144963030501769311835411762026907848397529006599563288690089282702818198177368099766733506715831007535690273535741585530721389732916130816863687011754081219886436105201386044253051204304648556642980507914261370486658516914518976
n: 607623369882890591735782141073772197087735470451907161056918749085797298608061697204877318116530061370098150393008398852309935398612508655661345572182951783541048774456584255774063319762705994011630127672153887410829669163686086432067585460780467260542209687551454132414709631582428726568293866157915237
e: 65537</p>
<p><strong>解题</strong></p>
<p>首先用<code>yafu</code>经过多次分解直到所有因子都为素数，可以得到 32 个素数因子，然后直接求解即可：</p>
<pre><code>from Crypto.Util.number import *
import gmpy2

c = 236434294562852381842307785543347919217676481857496426677823656807506421759144963030501769311835411762026907848397529006599563288690089282702818198177368099766733506715831007535690273535741585530721389732916130816863687011754081219886436105201386044253051204304648556642980507914261370486658516914518976
n = 607623369882890591735782141073772197087735470451907161056918749085797298608061697204877318116530061370098150393008398852309935398612508655661345572182951783541048774456584255774063319762705994011630127672153887410829669163686086432067585460780467260542209687551454132414709631582428726568293866157915237
e = 65537
factors = [2209835647, 3279221983, 2203115203, 3083863231, 2624125561, 4051923611, 3870883097, 3919135769, 3746033843, 2349626557, 2911452569, 2280078727, 3772965367, 2486744167, 3816147749, 2613884417, 2657517431, 2808514571, 3516405091, 3393739981, 2965911017, 2282964227, 2794765357, 2162896789, 4177000211, 2804308609, 2549752151, 2206071653, 2336473199, 2647948099, 3656705023, 2574736709]
phi = 1
for x in factors:
phi *= (x-1)
d = gmpy2.invert(e, phi)
print long_to_bytes(pow(c, d, n))
</code></pre>
<h3 id="p或q选取不当分解n"><a class="header" href="#p或q选取不当分解n">p或q选取不当分解N</a></h3>
<p>当 RSA 中 p 和 q 选取不当时，我们也可以进行攻击。比如一般有以下四种情况</p>
<h4 id="p-q-很大"><a class="header" href="#p-q-很大">$|p-q|$ 很大</a></h4>
<p>当$|p-q|$ 很大时，那么其中p或q有一个值一定很小，我们可以用试除法穷举p或q。</p>
<h4 id="p-q-较小"><a class="header" href="#p-q-较小">$|p-q|$ 较小</a></h4>
<p>参考：https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_module_attack-zh/#p-q_1</p>
<p><strong>例题：[GWCTF 2019]BabyRSA</strong></p>
<p>[GWCTF 2019]BabyRSA</p>
<p>题目描述：</p>
<pre><code>import hashlib
import sympy
from Crypto.Util.number import *

flag = 'GWHT{******}'
secret = '******'

assert(len(flag) == 38)

half = len(flag) / 2

flag1 = flag[:half]
flag2 = flag[half:]

secret_num = getPrime(1024) * bytes_to_long(secret)

p = sympy.nextprime(secret_num)
q = sympy.nextprime(p)
N = p * q
e = 0x10001

F1 = bytes_to_long(flag1)
F2 = bytes_to_long(flag2)

c1 = F1 + F2
c2 = pow(F1, 3) + pow(F2, 3)
assert(c2 &lt; N)

m1 = pow(c1, e, N)
m2 = pow(c2, e, N)

output = open('secret', 'w')
output.write('N=' + str(N) + '\n')
output.write('m1=' + str(m1) + '\n')
output.write('m2=' + str(m2) + '\n')
output.close()
</code></pre>
<p>题目解析：</p>
<p>因为p和q相差较小，一般来说相差千万都是比较小的，可以有两种解法</p>
<ol>
<li>我们对N开根号，然后从$\sqrt N$ 到$N$依此遍历</li>
<li>yafu分解</li>
</ol>
<p>解题：</p>
<pre><code>import gmpy2
from Crypto.Util.number import isPrime, long_to_bytes
from z3 import *

N = 636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163
e = 65537

m1 = 90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
m2 = 487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546

sqrt_N = gmpy2.iroot(N, 2)[0]

for i in range(sqrt_N, N):
if isPrime(i):
if N % i == 0:
p = i
q = N // i
break

phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
c1 = gmpy2.powmod(m1, d, N)
c2 = gmpy2.powmod(m2, d, N)

# 当前半部分计算出a和b后，使用z3分解
s = Solver()
F1, F2 = Ints('F1 F2')
s.add(F1 + F2 == 2732509502629189160482346120094198557857912754)
s.add(F1 ** 3 + F2 ** 3 == 5514544075236012543362261483183657422998274674127032311399076783844902086865451355210243586349132992563718009577051164928513093068525554)
if s.check() == sat:
F1 = (s.model()[F1]).as_long()
F2 = (s.model()[F2]).as_long()

flag1 = long_to_bytes(F1)
flag2 = long_to_bytes(F2)
flag = flag1 + flag2
print(flag)
</code></pre>
<h4 id="p-1光滑或p1光滑"><a class="header" href="#p-1光滑或p1光滑">$p-1$光滑或$p+1$光滑</a></h4>
<p>光滑数（Smooth Number）指可以分解为小素数乘积的正整数。</p>
<p>当 p 是 N 的因数，并且 $p−1$ 是光滑数，可能可以使用 Pollard’s p − 1 算法来分解 N。</p>
<h5 id="原理-1"><a class="header" href="#原理-1">原理</a></h5>
<p>根据费马小定理：</p>
<p>如果p是一个素数，而整数a不是p的倍数，则有 $a^{p-1} \equiv 1 \bmod p$</p>
<p>则：$a^{t(p-1)} \equiv 1^t \equiv 1 \bmod p$</p>
<p>可改为等式：$a^{t(p-1)} - 1 = k * p$</p>
<p>即$a^{t(p-1)} - 1$是p的倍数。</p>
<p>然后根据 Pollard’s p - 1 算法：</p>
<p>如果 p−1 是一些很小质数的乘积，那么 n! 就能被 p−1 整除。即 n!=t(p−1)。</p>
<p>对于每一个 n=2,3,4,…，任意选择一个底数 a（事实上，可以简单地选择为 2），并计算：</p>
<p>$gcd(a^{n!} - 1, N)$</p>
<p>如果结果不为 1 或 NNN，那么就已成功分解 NNN。</p>
<p>但n较大时，直接计算n!将会很消耗资源。在便利n时，可以简化运算。</p>
<p>因为：$a^{n!} \bmod N = (a \bmod N) ^ {n!} \bmod N$</p>
<p>所以：$a^{n!} \bmod N = \begin{cases} (a \bmod N) ^ 2 \bmod N &amp; \text{n = 2} \ (a^{(n-1)!} \bmod N) ^ n \bmod N &amp; \text{n &gt;= 3} \end{cases} $</p>
<h5 id="解题脚本"><a class="header" href="#解题脚本">解题脚本</a></h5>
<pre><code>import gmpy2

def Pollards_p_1(N):
a = 2
n = 2
while True:
a = pow(a, n, N)
res = gmpy2.gcd(a-1, N)
if res != 1 and res != N:
print 'n =', n
print 'p =', res
return res
n += 1
</code></pre>
<h5 id="nctf2019-childrsa"><a class="header" href="#nctf2019-childrsa">[NCTF2019] childRSA</a></h5>
<p><strong>题目</strong></p>
<pre><code>from random import choice
from Crypto.Util.number import isPrime, sieve_base as primes
from flag import flag

def getPrime(bits):
while True:
n = 2
while n.bit_length() &lt; bits:
n *= choice(primes)
if isPrime(n + 1):
return n + 1

e = 0x10001
m = int.from_bytes(flag.encode(), 'big')
p, q = [getPrime(2048) for _ in range(2)]
n = p * q
c = pow(m, e, n)
# n = 3284971819733758182300224371705765921850251900438699666088510059287220194883415554312592439561492896275057966734...388249513
# c = 2630801835673985389538224010996889417516673128370292700216526899877370833521633899705831415771714713108329655131...605279108
</code></pre>
<p><strong>解题</strong></p>
<p>可以发现 p 和 q 是由前10000个随机的许多小质数乘积加1得到，即p−1为许多小质数的乘积。那么可以利用Pollard’s p − 1 算法来分解 N。</p>
<pre><code>e = 0x10001
n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108

p = pollards_p_1(n)
q = n // p
assert p*q == n
d = gmpy2.invert(e, (p-1)*(q-1))
m = pow(c, d, n)
print(long_to_bytes(m))
</code></pre>
<h3 id="模不互素"><a class="header" href="#模不互素">模不互素</a></h3>
<h4 id="可攻击特征-2"><a class="header" href="#可攻击特征-2">可攻击特征</a></h4>
<p>当存在两个公钥的 N 不互素时</p>
<h4 id="原理-2"><a class="header" href="#原理-2">原理</a></h4>
<p>当存在两个公钥的 N 不互素时，我们显然可以直接对这两个数求最大公因数，然后直接获得 p，q，进而获得相应的私钥。具体来说：</p>
<p>当$n1 = p1 * q1$，$n2 = p1 * q2$ 时，我们先求出p1，然后再求出对应的q1和q2即可。</p>
<h4 id="sctf-rsa2"><a class="header" href="#sctf-rsa2">SCTF-RSA2</a></h4>
<p>题目链接：https://github.com/ohroot/rsatools/blob/master/demos/sctf/rsa2/syc_security_system_traffic2.pcap</p>
<p>题目描述：题目是一个流量包，我们从中提取出两个</p>
<p><strong>解题</strong></p>
<pre><code>import gmpy2
from Crypto.Util.number import long_to_bytes

n1 = 20823369114556260762913588844471869725762985812215987993867783630051420241057912385055482788016327978468318067078233844052599750813155644341123314882762057524098732961382833215291266591824632392867716174967906544356144072051132659339140155889569810885013851467056048003672165059640408394953573072431523556848077958005971533618912219793914524077919058591586451716113637770245067687598931071827344740936982776112986104051191922613616045102859044234789636058568396611030966639561922036712001911238552391625658741659644888069244729729297927279384318252191421446283531524990762609975988147922688946591302181753813360518031
n2 = 19083821613736429958432024980074405375408953269276839696319265596855426189256865650651460460079819368923576109723079906759410116999053050999183058013281152153221170931725172009360565530214701693693990313074253430870625982998637645030077199119183041314493288940590060575521928665131467548955951797198132001987298869492894105525970519287000775477095816742582753228905458466705932162641076343490086247969277673809512472546919489077884464190676638450684714880196854445469562733561723325588433285405495368807600668761929378526978417102735864613562148766250350460118131749533517869691858933617013731291337496943174343464943

p1 = gmpy2.gcd(n1, n2)
q1 = n1 // p1
e = 65537
phi = (p1 - 1) * (q1 - 1)
d = gmpy2.invert(e, phi)
cipher = 0x68d5702b70d18238f9d4a3ac355b2a8934328250efd4efda39a4d750d80818e6fe228ba3af471b27cc529a4b0bef70a2598b80dd251b15952e6a6849d366633ed7bb716ed63c6febd4cd0621b0c四ebfe5235de03d4ee016448de1afbbe61144845b580eed8be8127a8d92b37f9ef670b3cdd5af613c76f58ca1a9f6f03f1bc11addba30b61bb191efe0015e971b8f78375faa257a60b355050f6435d94b49eab07075f40cb20bb8723d02f5998d5538e8dafc80cc58643c91f6c0868a7a7bf3bf6a9b4b6e79e0a80e89d430f0c049e1db4883c50db066a709b89d74038c34764aac286c36907b392bc299ab8288f9d7e372868954a92cdbf634678f7294096c7
plain = gmpy2.powmod(cipher, d, n1)
print(long_to_bytes(plain))
</code></pre>
<h3 id="共模攻击"><a class="header" href="#共模攻击">共模攻击</a></h3>
<h4 id="可攻击特征-3"><a class="header" href="#可攻击特征-3">可攻击特征</a></h4>
<p>当两个用户使用相同的模数 N、不同的私钥时，加密同一明文消息时即存在共模攻击。</p>
<p>具体说就是：明文m、模数n相同，公钥指数e、密文c不同，gcd(e1,e2)==1也就是e1和e2互质时候，可能导致共模攻击。</p>
<h4 id="原理-3"><a class="header" href="#原理-3">原理</a></h4>
<p>设两个用户的公钥分别为 $e_1$ 和 $e_2$，且两者互质。明文消息为 $m$，密文分别为：</p>
<p>$$ c_1 = m^{e_1}\bmod N $$</p>
<p>$$ c_2 = m^{e_2}\bmod N $$</p>
<p>当攻击者截获 $c_1$ 和 $c_2$ 后，就可以恢复出明文。用扩展欧几里得算法求出 $re_1+se_2=1\bmod n$ 的两个整数 $r$ 和 $s$，由此可得：</p>
<p>$$ c{1}^{r}c{2}^{s} \equiv m^{re_1}m^{se_2}\bmod n\ $$</p>
<p>$$ c{1}^{r}c{2}^{s}\equiv m^{(re_1+se_2)} \bmod n\ $$</p>
<p>$$c{1}^{r}c{2}^{s}\equiv m\bmod n $$</p>
<h4 id="jarvisoj-very-hard-rsa"><a class="header" href="#jarvisoj-very-hard-rsa">jarvisoj-very hard RSA</a></h4>
<p><strong>题目描述</strong></p>
<p>前几题因为N太小，都被你攻破了，出题人这次来了个RSA4096，是否接受挑战就看你了。</p>
<pre><code>#!/usr/bin/env python

import random

N = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c四78bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L

def pad_even(x):
return ('', '0')[len(x)%2] + x

e1 = 17
e2 = 65537


fi = open('flag.txt','rb')
fo1 = open('flag.enc1','wb')
fo2 = open('flag.enc2','wb')


data = fi.read()
fi.close()

while (len(data)&lt;512-11):
data  =  chr(random.randint(0,255))+data

data_num = int(data.encode('hex'),16)

encrypt1 = pow(data_num,e1,N)
encrypt2 = pow(data_num,e2,N)


fo1.write(pad_even(format(encrypt1,'x')).decode('hex'))
fo2.write(pad_even(format(encrypt2,'x')).decode('hex'))

fo1.close()
fo2.close()
</code></pre>
<p><strong>题目分析</strong></p>
<p>题目中4096位的RSA加密，硬解肯定是解不开的。我们观察题目特点，题目给出了2个flag.enc文件和一个easyRSA.py的脚本。分析该脚本</p>
<p><strong>解题</strong></p>
<pre><code>import gmpy2
from Crypto.Util.number import long_to_bytes,bytes_to_long

e1 = 17
e2 = 65537
n = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c四78bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929

with open('./flag.enc1','rb') as enc1:
c1 = bytes_to_long(enc1.read())
with open('./flag.enc2','rb') as enc2:
c2 = bytes_to_long(enc2.read())

_, r, s = gmpy2.gcdext(e1, e2)
m = gmpy2.powmod(c1, r, n) * gmpy2.powmod(c2, s, n) % n
print(long_to_bytes(m))
</code></pre>
<h2 id="公钥指数e的相关攻击"><a class="header" href="#公钥指数e的相关攻击">公钥指数e的相关攻击</a></h2>
<h3 id="小公钥指数攻击"><a class="header" href="#小公钥指数攻击">小公钥指数攻击</a></h3>
<h4 id="可攻击特征-4"><a class="header" href="#可攻击特征-4">可攻击特征</a></h4>
<p>e 特别小，比如 e 为 3。</p>
<h4 id="原理-4"><a class="header" href="#原理-4">原理</a></h4>
<p>假设用户使用的密钥 $e=3$，考虑到加密关系满足：</p>
<p>$c\equiv m^3 \bmod N$</p>
<p>则：</p>
<p>$$\begin{align} m^3 &amp;= c+k\times N\ m &amp;= \sqrt[3]{c+k\times n} \end{align}$$</p>
<h4 id="jarvisoj-extremely-hard-rsa"><a class="header" href="#jarvisoj-extremely-hard-rsa">jarvisoj-Extremely hard RSA</a></h4>
<p><strong>题目描述</strong></p>
<p>没想到RSA4096都被你给破了，一定是我的问题，给了你太多信息，这次我只给你一个flag的加密值和公钥，仍然是RSA4096，我就不信你还能解出来。</p>
<p>题目附件是两个文件：<code>pubkey.pem</code>、<code>flag.enc</code></p>
<p><strong>解题</strong></p>
<p>首先我们使用openssl工具查看公钥文件的一些参数（为了节省篇幅，省略一些解题无关的内容）</p>
<p>➜  [Jarvis OJ]extremelyhardRSA openssl rsa -pubin -in pubkey.pem -text -modulus
Public-Key: (4096 bit)
Modulus:
00:b0:be:e5:e3:e9:e5:a7:e8:d0:0b:49:33:55:c6:
…
Exponent: 3 (0x3)
Modulus=B0BEE5E3E9E5A7E8D00B493355C618FC8C7D7D03B82E409951C182F398DEE3104580E7BA70D383AE5311475656E8A964D380CB157F48C951ADFA65DB0B122CA40E42FA709189B719A4F0D746E2F6069BAF11CEBD650F14B93C977352FD13B1EEA6D6E1DA775502ABFF89D3A8B3615FD0DB49B88A976BC20568489284E181F6F11E270891C8EF80017BAD238E363039A458470F1749101BC29949D3A4F4038D463938851579C7525A69984F15B5667F34209B70EB261136947FA123E549DFFF00601883AFD936FE411E006E4E93D1A00B0FEA541BBFC8C5186CB6220503A94B2413110D640C77EA54BA3220FC8F4CC6CE77151E29B3E06578C四78BD1BEBE04589EF9A197F6F806DB8B3ECD826CAD24F5324CCDEC6E8FEAD2C2150068602C8DCDC59402CCAC9424B790048CCDD9327068095EFA010B7F196C74BA8C37B128F9E1411751633F78B7B9E56F71F77A1B4DAAD3FC54B5E7EF935D9A72FB176759765522B4BBC02E314D5C06B64D5054B7B096C601236E6CCF45B5E611C805D335DBAB0C35D226CC208D8CE4736BA39A0354426FAE006C7FE52D5267DCFB9C3884F51FDDFDF4A9794BCFE0E1557113749E6C8EF421DBA263AFF68739CE00ED80FD0022EF92D3488F76DEB62BDEF7BEA6026F22A1D25AA2A92D124414A8021FE0C174B9803E6BB5FAD75E186A946A17280770F1243F4387446CCCEB2222A965CC30B3929
writing RSA key
—–BEGIN PUBLIC KEY—–
MIICIDANBgkqhkiG9w0BAQEFAAOCAg0AMIICCAKCAgEAsL7l4+nlp+jQC0kzVcYY
…</p>
<p>写出脚本</p>
<pre><code>import gmpy2
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long,long_to_bytes
from multiprocessing import Pool
pool = Pool(4)

with open('./pubkey.pem', 'r') as f:
key = RSA.importKey(f.read())
N = key.n
e = key.e
with open('flag.enc', 'rb') as f:
cipher = bytes_to_long(f.read())

def calc(j):
a, b = gmpy2.iroot(cipher + j * N, 3)
if b == 1:
m = long_to_bytes(a)
print(m)
pool.terminate()
exit()

def main():
inputs = range(0, 150000000)
pool.map(calc, inputs)
pool.close()
pool.join()

if __name__ == '__main__':
print('start')
main()
</code></pre>
<h3 id="小公钥指数攻击之rabin-算法"><a class="header" href="#小公钥指数攻击之rabin-算法">小公钥指数攻击之Rabin 算法</a></h3>
<h4 id="可攻击特征-5"><a class="header" href="#可攻击特征-5">可攻击特征</a></h4>
<p>Rabin 算法的特征在于 $e=2$。</p>
<h4 id="原理-5"><a class="header" href="#原理-5">原理</a></h4>
<p>暂略，数学推导。</p>
<h4 id="jarvisoj-extremely-hard-rsa-1"><a class="header" href="#jarvisoj-extremely-hard-rsa-1">jarvisoj-Extremely hard RSA</a></h4>
<pre><code>import gmpy2
import string
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long,long_to_bytes

# 读取公钥参数
with open('pubkey.pem', 'r') as f:
key = RSA.importKey(f.read())
N = key.n
e = key.e
with open('flag.enc', 'rb') as f:
cipher = bytes_to_long(f.read())

p=275127860351348928173285174381581152299
q=319576316814478949870590164193048041239
e = 2

# 计算yp和yq
inv_p = gmpy2.invert(p, q)
inv_q = gmpy2.invert(q, p)

# 计算mp和mq
mp = pow(cipher, (p + 1) // 4, p)
mq = pow(cipher, (q + 1) // 4, q)

# 计算a,b,c,d
a = (inv_p * p * mq + inv_q * q * mp) % N
b = N - int(a)
c = (inv_p * p * mq - inv_q * q * mp) % N
d = N - int(c)

for i in (a, b, c, d):
print(long_to_bytes(i))
</code></pre>
<h3 id="私钥指数d的相关攻击"><a class="header" href="#私钥指数d的相关攻击">私钥指数d的相关攻击</a></h3>
<h4 id="可攻击特征-6"><a class="header" href="#可攻击特征-6">可攻击特征</a></h4>
<p>首先当 d 泄露之后，我们自然可以解密所有加密的消息。我们甚至还可以对模数 N 进行分解。</p>
<h4 id="原理-6"><a class="header" href="#原理-6">原理</a></h4>
<p>我们知道 $ed \equiv 1 \bmod \varphi(n)$，那么存在一个 $k$ 使得</p>
<p>$ed-1=k\varphi(n)$</p>
<p>又 $\forall a\in {Z}_n^*$，满足 $a^{ed-1}\equiv1(\bmod n)$ 。令</p>
<p>$ed-1=2^st$</p>
<p>其中，$t$ 是一个奇数。然后可以证明对于至少一半的 $a\in {Z}_n^*$，存在一个 $i\in[1,s]$，使得</p>
<p>$a^{2^{i-1}t}\not\equiv\pm1(\bmod n),a^{2^{i}t}\equiv1(\bmod n)$</p>
<p>成立。如果 $a,i$ 满足上述条件，$gcd(a^{2^{i-1}t}-1,n)$ 是 $n$ 的一个非平凡因子，所以可以对 $n$ 进行暴力分解。</p>
<p>可参考：https://www.di-mgt.com.au/rsa_factorize_n.html</p>
<h4 id="攻击脚本"><a class="header" href="#攻击脚本">攻击脚本</a></h4>
<pre><code>#!/usr/bin/env python3
import random
import gmpy2
def divide_pq(ed, n):
# ed = e*d
k = ed - 1
while True:
g = random.randint(3, n-2)
t = k
while True:
if t % 2 != 0:
break
t = t//2
x = pow(g, t, n)
if x &gt; 1 and gmpy2.gcd(x-1, n) &gt; 1:
p = gmpy2.gcd(x-1, n)
return (p, n//p)
</code></pre>
<h4 id="工具"><a class="header" href="#工具">工具</a></h4>
<p>也可以使用如下工具可以直接进行计算</p>
<ul>
<li>RsaConverter.exe (<a href="https://sourceforge.net/projects/rsaconverter/">https://sourceforge.net/projects/rsaconverter/</a>, for windows )</li>
<li><a href="https://github.com/ius/rsatool/blob/master/rsatool.py">rsatool.py</a>(分解原理如上)</li>
</ul>
<h3 id="wieners-attack"><a class="header" href="#wieners-attack">Wiener’s Attack</a></h3>
<h4 id="可攻击特征-7"><a class="header" href="#可攻击特征-7">可攻击特征</a></h4>
<p>在 d 比较小 $d&lt;\frac{1}{3}N^{\frac{1}{4}}$ 时，攻击者可以使用 <strong>Wiener’s Attack</strong>来获得私钥。</p>
<blockquote>
<p>flatcc备注：e特别大时候也能解？</p>
</blockquote>
<h4 id="攻击原理"><a class="header" href="#攻击原理">攻击原理</a></h4>
<ul>
<li>https://sagi.io/2016/04/crypto-classics-wieners-rsa-attack/</li>
</ul>
<h4 id="2016-hctf-rsa1"><a class="header" href="#2016-hctf-rsa1">2016 HCTF RSA1</a></h4>
<p>这道题目也是从CTF-WiKi上边摘录的，题目是2016 年 HCTF 中 RSA 1 - Crypto So Interesting，源码链接在这里：https://github.com/Hcamael/ctf-library/tree/master/RSA1</p>
<p><strong>题目描述</strong></p>
<p>我们直接入手题目核心部分，先来看下题目给出的已知条件，题目内容如下：</p>
<pre><code>#  节选部分内容，下边是题目给出的n和e
p=getPrime(2048)
q=getPrime(2048)
n = p * q
e, d = get_ed(p, q)
print &quot;n: &quot;, hex(n)
print &quot;e: &quot;, hex(e)

# 下边是e,d的由来
def get_ed(p, q):
k = cal_bit(q*p)
phi_n = (p-1)*(q-1)
r = random.randint(10, 99)
while True:
u = getPrime(k/4 - r)
if gcd(u, phi_n) != 1:
continue
t = invmod(u, phi_n)
e = pi_b(t)
if gcd(e, phi_n) == 1:
break
d = invmod(e, phi_n)
return (e, d)
</code></pre>
<p><strong>解题思路</strong></p>
<p>所以从<code>get_ed()</code>这个函数，我们得知u的位数小于四分之一的n，那么我们就想到了Wiener’s Attack攻击，使用t和n求出u；但要得先求出t来，我们从题目中得知<code>e = pi_b(t)</code>，那么e是又是已知的，这个问题就解决了。</p>
<p><strong>解题脚本</strong></p>
<p>在自己的<code>rsa_toolset/RSA-Wiener-Attack/exp.py</code></p>
<pre><code>def wiener_hack(e, n):
# firstly git clone https://github.com/pablocelayes/rsa-wiener-attack.git !
frac = ContinuedFractions.rational_to_contfrac(e, n)
convergents = ContinuedFractions.convergents_from_contfrac(frac)
for (k, d) in convergents:
if k != 0 and (e * d - 1) % k == 0:
phi = (e * d - 1) // k
s = n - phi + 1
discr = s * s - 4 * n
if (discr &gt;= 0):
t = Arithmetic.is_perfect_square(discr)
if t != -1 and (s + t) % 2 == 0:
print(&quot;Hacked!&quot;)
return d
return False
</code></pre>
<h2 id="coppersmith-相关攻击"><a class="header" href="#coppersmith-相关攻击">Coppersmith 相关攻击</a></h2>
<p>相关数学理论基础可参考：https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_coppersmith_attack-zh/</p>
<p><strong>Coppersmith method</strong>可参考：https://github.com/mimoo/RSA-and-LLL-attacks</p>
<h3 id="basic-broadcast-attack"><a class="header" href="#basic-broadcast-attack">Basic Broadcast Attack</a></h3>
<p>中文有人翻译作广播攻击</p>
<h4 id="可攻击特征-8"><a class="header" href="#可攻击特征-8">可攻击特征</a></h4>
<p>如果一个用户使用同一个加密指数 e 加密了同一个密文，并发送给了其他 e 个用户。那么就会产生广播攻击。这一攻击由 Håstad 提出。</p>
<h4 id="原理-7"><a class="header" href="#原理-7">原理</a></h4>
<p>这里我们假设 e 为 3，并且加密者使用了三个不同的模数 $n_1,n_2,n_3$ 给三个不同的用户发送了加密后的消息 m，如下</p>
<p>$$ \begin{align} c_1 &amp;=m^3\bmod n_1\ c_2&amp;=m^3\bmod n_2\ c_3&amp;=m^3\bmod n_3 \end{align} $$</p>
<p>这里我们假设 $n_1,n_2,n_3$ 互素，不然，我们就可以直接进行分解，然后得到 d，进而然后直接解密。</p>
<p>同时，我们假设 $m&lt;n_i, 1\leq i \leq 3$。如果这个条件不满足的话，就会使得情况变得比较复杂，这里我们暂不讨论。</p>
<p>既然他们互素，那么我们可以根据中国剩余定理，可得$m^3 \equiv C \bmod n_1n_2n_3$。</p>
<p>此外，既然 $m&lt;n_i, 1\leq i \leq 3$，那么我们知道 $m^3 &lt; n_1n_2n_3$ 并且 $C&lt;m^3 &lt; n_1n_2n_3$，那么 $m^3 = C$，我们对 C 开三次根即可得到 m 的值。</p>
<p>对于较大的 e 来说，我们只是需要更多的明密文对。</p>
<h4 id="buuctf-rsa4"><a class="header" href="#buuctf-rsa4">BUUCTF-RSA4</a></h4>
<p><strong>题目</strong></p>
<p>题目就给出了几个数字对</p>
<p>N = 331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004
c = 310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243</p>
<p>N = 302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114
c = 112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344</p>
<p>N = 332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323
c = 10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242</p>
<p><strong>解题</strong></p>
<p>解题我们用脚本跑一下即可，但要注意此题所给的数都是5进制的。</p>
<h3 id="broadcast-attack-with-linear-padding"><a class="header" href="#broadcast-attack-with-linear-padding">Broadcast Attack with Linear Padding</a></h3>
<p>待补充</p>
<h3 id="related-message-attack"><a class="header" href="#related-message-attack">Related Message Attack</a></h3>
<h4 id="可攻击特征-9"><a class="header" href="#可攻击特征-9">可攻击特征</a></h4>
<p>当 Alice 使用同一公钥对两个具有某种线性关系的消息 M1 与 M2 进行加密，并将加密后的消息 C1，C2 发送给了 Bob 时，我们就可能可以获得对应的消息 M1 与 M2。这里我们假设模数为 N，两者之间的线性关系如下</p>
<p>$$ M_1 \equiv f(M_2) \bmod N $$</p>
<p>其中 f 为一个线性函数，比如说 $f=ax+b$。</p>
<h4 id="原理-8"><a class="header" href="#原理-8">原理</a></h4>
<p>首先，我们知道 $C_1 \equiv M_1 ^e \bmod N$，并且 $M_1 \equiv f(M_2) \bmod N$，那么我们可以知道 $M_2$ 是 $f(x)^e \equiv C_1 \bmod N$ 的一个解，即它是方程 $f(x)^e-C_1$ 在模 N 意义下的一个根。同样的，$M_2$ 是 $x^e - C_2$ 在模 N 意义下的一个根。所以说 $x-M_2$ 同时整除以上两个多项式。因此，我们可以求得两个多项式的最大公因子，如果最大公因子恰好是线性的话，那么我们就求得了 $M_2$。需要注意的是，在 $e=3$ 的情况下，最大公因子一定是线性的。</p>
<p>这里我们关注一下 $e=3$，且 $f(x)=ax+b$ 的情况。首先我们有</p>
<p>$$ C_1 \equiv M_1 ^3 \bmod N,M_1 \equiv aM_2+b \bmod N $$</p>
<p>那么我们有</p>
<p>$$ C_1 \equiv (aM_2+b)^3 \bmod N,C_2 \equiv M_2^3 \bmod N $$</p>
<p>我们需要明确一下我们想要得到的是消息 m，所以需要将其单独构造出来。</p>
<p>首先，我们有式 1</p>
<p>$$ (aM_2+b)^3=a^3M_2^3+3a^2M^2b+3aM_2b^2+b^3 $$</p>
<p>再者我们构造如下式 2</p>
<p>$$ (aM_2)^3-b^3 \equiv (aM_2-b)(a^2M_2^2+aM_2b+b^2) \bmod N $$</p>
<p>根据式 1 我们有</p>
<p>$$ a^3M_2^3-2b^3+3b(a^2M_2^2+aM_2b+b^2) \equiv C_1 \bmod N $$</p>
<p>继而我们有式 3</p>
<p>$$ 3b(a^2M_2^2+aM_2b+b^2) \equiv C_1-a^3C_2+2b^3 \bmod N $$</p>
<p>那么我们根据式 2 与式 3 可得</p>
<p>$$ (a^3C_2-b^3)*3b \equiv (aM_2-b)( C_1-a^3C_2+2b^3 ) \bmod N $$</p>
<p>进而我们有</p>
<p>$$ aM_2-b=\frac{3a^3bC_2-3b^4}{C_1-a^3C_2+2b^3} $$</p>
<p>进而</p>
<p>$$ aM_2\equiv \frac{2a^3bC_2-b^4+C_1b}{C_1-a^3C_2+2b^3} $$</p>
<p>进而</p>
<p>$$ M_2 \equiv\frac{2a^3bC_2-b^4+C_1b}{aC_1-a^4C_2+2ab^3}=\frac{b}{a}\frac{C_1+2a^3C_2-b^3}{C_1-a^3C_2+2b^3} $$</p>
<p>上面的式子中右边所有的内容都是已知的内容，所以我们可以直接获取对应的消息。</p>
<p>有兴趣的可以进一步阅读 A New Related Message Attack on RSA 以及 paper 这里暂不做过多的讲解。</p>
<h4 id="sctf-rsa3"><a class="header" href="#sctf-rsa3">SCTF-RSA3</a></h4>
<p><strong>题目链接</strong>https://github.com/ohroot/rsatools/tree/master/demos/sctf/rsa3</p>
<p><strong>题目</strong>题目给出的是一个TCP的流量包，跟随数据流我们可以看到其中的N，user_id，密文C</p>
<p><strong>解题</strong>我们取其中模N相同的0组和9组数据，按照上边的公式，写出解密脚本如下</p>
<pre><code>#!/usr/bin/env python3
import gmpy2
from Crypto.Util.number import long_to_bytes

id1 = 1002
id2 = 2614

c1 = 0x547995f4e2f4c007e6bb2a6913a3d685974a72b05bec02e8c03ba64278c9347d8aaaff672ad8460a8cf5bffa5d787c5bb724d1cee07e221e028d9b8bc24360208840fbdfd4794733adcac四5c38ad0225fde19a6a4c38e4207368f5902c871efdf1bdf4760b1a98ec1417893c8fce8389b6434c0fee73b13c284e8c9fb5c77e420a2b5b1a1c10b2a7a3545e95c1d47835c2718
c2 = 0x547995f4e2f4c007e6bb2a6913a3d685974a72b05bec02e8c03ba64278c9347d8aaaff672ad8460a8cf5bffa5d787c72722fe4fe5a901e2531b3dbcb87e5aa19bbceecbf9f32eacefe81777d9bdca781b1ec8f8b68799b4aa4c6ad120506222c7f0c3e11b37dd0ce08381fabf9c14bc74929bf524645989ae2df77c8608d0512c1cc四150765ab8350843b57a2464f848d8e08
n = 25357901189172733149625332391537064578265003249917817682864120663898336510922113258397441378239342349767317285221295832462413300376704507936359046120943334215078540903962128719706077067557948218308700143138420408053500628616299338204718213283481833513373696170774425619886049408103217179262264003765695390547355624867951379789924247597370496546249898924648274419164899831191925127182066301237673243423539604219274397539786859420866329885285232179983055763704201023213087119895321260046617760702320473069743688778438854899409292527695993045482549594428191729963645157765855337481923730481041849389812984896044723939553
a = 1
b = id1 - id2
</code></pre>
<h1 id="套公式"><a class="header" href="#套公式">套公式</a></h1>
<pre><code>def getmessage(a, b, c1, c2, n):
b3 = gmpy2.powmod(b, 3, n)
part1 = b * (c1 + 2 * c2 - b3) % n
part2 = a * (c1 - c2 + 2 * b3) % n
part2 = gmpy2.invert(part2, n)
return part1 * part2 % n

message = getmessage(a, b, c1, c2, n) - id2
print(long_to_bytes(message))
</code></pre>
<h3 id="coppersmiths-short-pad-attack"><a class="header" href="#coppersmiths-short-pad-attack">Coppersmith’s short-pad attack</a></h3>
<h4 id="可攻击特征-10"><a class="header" href="#可攻击特征-10">可攻击特征</a></h4>
<p>过短的padding长度导致的容易攻击</p>
<h3 id="known-high-bits-message-attackstereotyped-messages"><a class="header" href="#known-high-bits-message-attackstereotyped-messages">Known High Bits Message Attack(Stereotyped messages)</a></h3>
<h4 id="可攻击特征-11"><a class="header" href="#可攻击特征-11">可攻击特征</a></h4>
<ul>
<li>如果e较小，并且已知m的高位，则可通过此方法求出完整的m。</li>
<li>比如题目给出m=0x65c四6754a7776c8b88867e000000000000000000 前面的部分就是高位，后面的0就是低位，0只是占位的作用并不是真正m的值。</li>
</ul>
<h4 id="原理-9"><a class="header" href="#原理-9">原理</a></h4>
<p>知道了消息m的很大一部分$m_0$</p>
<p>现在，$c=(m_0+x)^e\mod n$，也就是 $f(x)=(m + x)^e - c$ 有一个解满足 $f(x)=k\cdot N(k=0,1,2\cdots)$ ,求解x。</p>
<p>依据coppersmith定理是可以求出剩下的所有明文部分。</p>
<h4 id="解题方法"><a class="header" href="#解题方法">解题方法</a></h4>
<p>在线sagemath：https://sagecell.sagemath.org/</p>
<p>自己安装的离线sage</p>
<h4 id="2019强网杯copperstudylevel1"><a class="header" href="#2019强网杯copperstudylevel1">2019强网杯copperstudy—level1</a></h4>
<p><strong>题目</strong></p>
<p>n=0xa1888c641a05aeb81b3d1686317a86f104791fe1d570a5b11209f45d09ea401d255a70744e7a2d39520e359c23a9f1209ee47f496dbd279e62ee1648b3a277ced8825298274322e0a7a86deea282676310a73b6bb946fc924c34ac6c8784ff559bf9a004c03fb167ef54aaea90ce587f2f3074b40d7f632022ec8fb12e659953L  
e=3  
m=random.getrandbits(512)  
c=pow(m,e,n)=0x93145ece45f416a11e5e9475518f165365456183c361500c2f78aff263028c90f20b7d97205f54e21f3bcc8a556b457889fde3719d0a0f9c9646f3f0d0a1e4bee0f259f023168fe8cc0511848c1635022fcc20b6088084585e2f8055a9d1b1d6bdb228087900bf7c6d42298f8e45c四51562c816e2303990834c94e580bf0cbd1L  
((m&gt;&gt;72)&lt;&lt;72)=0x9e67d3a220a3dcf6fc四742052621f543b8c78d5d9813e69272e65ac676672446e5c88887e8bfdfc92ec87ec74c16350e6b539e3bd910b000000000000000000L</p>
<p><strong>解题思路</strong></p>
<p>要求求出完整的m，很明显e较小，并且已知了m的高位，我们通过CopperSmith算法的Stereotyped messages Attack获得完整的m。</p>
<p><strong>解题脚本</strong></p>
<pre><code># exp.sage
load(&quot;coppersmith_py3.sage&quot;)
N = 0xa1888c641a05aeb81b3d1686317a86f104791fe1d570a5b11209f45d09ea401d255a70744e7a2d39520e359c23a9f1209ee47f496dbd279e62ee1648b3a277ced8825298274322e0a7a86deea282676310a73b6bb946fc924c34ac6c8784ff559bf9a004c03fb167ef54aaea90ce587f2f3074b40d7f632022ec8fb12e659953
e = 3
m = 0x9e67d3a220a3dcf6fc四742052621f543b8c78d5d9813e69272e65ac676672446e5c88887e8bfdfc92ec87ec74c16350e6b539e3bd910b000000000000000000

c = 0x93145ece45f416a11e5e9475518f165365456183c361500c2f78aff263028c90f20b7d97205f54e21f3bcc8a556b457889fde3719d0a0f9c9646f3f0d0a1e4bee0f259f023168fe8cc0511848c1635022fcc20b6088084585e2f8055a9d1b1d6bdb228087900bf7c6d42298f8e45c四51562c816e2303990834c94e580bf0cbd1
ZmodN = Zmod(N)
P.&lt;x&gt; = PolynomialRing(ZmodN)
f = (m + x)^e - c
dd = f.degree()
beta = 1
epsilon = beta / 7
mm = ceil(beta**2 / (dd * epsilon))
tt = floor(dd * mm * ((1/beta) - 1))
XX = ceil(N**((beta**2/dd) - epsilon))
roots = coppersmith_howgrave_univariate(f, N, beta, mm, tt, XX)
print(&quot;结果是:&quot;, hex(roots[0]))  # 注意输出结果是16进制数
</code></pre>
<p>运行方式：<code>sage exp.sage</code></p>
<h3 id="factoring-with-high-bits-known-attack"><a class="header" href="#factoring-with-high-bits-known-attack">Factoring with High Bits Known Attack</a></h3>
<h4 id="可攻击特征-12"><a class="header" href="#可攻击特征-12">可攻击特征</a></h4>
<ul>
<li>已知公钥中模数 N 的一个因子的较高位时，我们就有一定几率来分解 N，例如已知p的高位。</li>
</ul>
<h4 id="攻击方法-1"><a class="header" href="#攻击方法-1">攻击方法</a></h4>
<p>sage脚本</p>
<h4 id="2019强网杯copperstudylevel2"><a class="header" href="#2019强网杯copperstudylevel2">2019强网杯copperstudy—level2</a></h4>
<p><strong>题目</strong></p>
<p>n=0x241ac918f708fff645d3d6e24315e5bb045c02e788c2b7f74b2b83484ce9c0285b6c54d99e2a601a386237d666db2805175e7cc86a733a97aeaab63486133103e30c1dca09741819026bd3ea8d08746d1d38df63c025c1793bdc7e38d194a30b492aadf9e31a6c1240a65db49e061b48f1f2ae949ac9e7e0992ed24f9c01578dL  
e=65537  
m=random.getrandbits(512)  
c=pow(m,e,n)=0x1922e7151c779d6bb554cba6a05858415e74739c36df0bcf169e49ef0e566a4353c51a306036970005f2321d1d104f91a673f40944e830619ed683d8f84eaf26e7a93c四abe1dbd7ca3babf3f4959def0e3d87f7818d54633a790fc74e9fed3c5b5456c21e3f425240f6217b0b14516cb59aa0ce74b83ca17d8cc四a0fbc829fb8L  
((p&gt;&gt;128)&lt;&lt;128)=0x2c1e75652df018588875c7ab60472abf26a234bc1bfc1b685888fb5ded29ab5b93f5105c1e9b46912368e626777a873200000000000000000000000000000000L</p>
<p><strong>解题脚本</strong></p>
<pre><code>n = 0x241ac918f708fff645d3d6e24315e5bb045c02e788c2b7f74b2b83484ce9c0285b6c54d99e2a601a386237d666db2805175e7cc86a733a97aeaab63486133103e30c1dca09741819026bd3ea8d08746d1d38df63c025c1793bdc7e38d194a30b492aadf9e31a6c1240a65db49e061b48f1f2ae949ac9e7e0992ed24f9c01578d
p_fake = 0x2c1e75652df018588875c7ab60472abf26a234bc1bfc1b685888fb5ded29ab5b93f5105c1e9b46912368e626777a873200000000000000000000000000000000

pbits = 1024  
kbits = 130  
pbar = p_fake &amp; (2^pbits-2^kbits)  
print(&quot;upper %d bits (of %d bits) is given&quot; % (pbits-kbits, pbits))

PR.&lt;x&gt; = PolynomialRing(Zmod(n))  
f = x + pbar  

x0 = f.small_roots(X=2^kbits, beta=0.4)[0]  # find root &lt; 2^kbits with factor &gt;= n^0.3  
print(hex(int(x0 + pbar)))
</code></pre>
<p>计算结果：</p>
<p>➜  RSA-and-LLL-attacks sage factoring_with_high_bits_know.sage
upper 894 bits (of 1024 bits) is given
0x2c1e75652df018588875c7ab60472abf26a234bc1bfc1b685888fb5ded29ab5b93f5105c1e9b46912368e626777a87321efe89ec89bdf3e4d9da9a45df22a787</p>
<h3 id="boneh-and-durfee-attack"><a class="header" href="#boneh-and-durfee-attack">Boneh and Durfee attack</a></h3>
<h4 id="可攻击特征-13"><a class="header" href="#可攻击特征-13">可攻击特征</a></h4>
<p>当 d 较小时，满足$d &lt; N^{0.292}$ 时，我们可以利用该攻击，比 Wiener’s Attack 要强一些。</p>
<h3 id="partial-key-exposure-attack"><a class="header" href="#partial-key-exposure-attack">Partial Key Exposure Attack</a></h3>
<h4 id="可攻击特征-14"><a class="header" href="#可攻击特征-14">可攻击特征</a></h4>
<ul>
<li>题目给出一组公钥n,e以及加密后的密文</li>
<li>若e较小，已知d的低位，则可通过此方法求出完整的d。</li>
</ul>
<h4 id="2019强网杯copperstudylevel3"><a class="header" href="#2019强网杯copperstudylevel3">2019强网杯copperstudy—level3</a></h4>
<p><strong>题目</strong></p>
<p>n=0x51fb3416aa0d71a430157d7c9853602a758e15462e7c08827b04cd3220c四27bbb8199ed4f5393dae43f013b68732a685defc17497f0912c886fa780dfacdfbb1461197d95a92a7a74ade874127a61411e14a901382ed3fb9d62c040c0dbaa374b5a4df06481a26da3fca271429ff10a4fc973b1c82553e3c1dd4f2f37dc24b3bL  </p>
<p>e=3  
m=random.getrandbits(512)  
c=pow(m,e,n)=0x3d7e16fd8b0b1afdb4e12594c3d8590f1175800ef07bb275d7a8ad983d0d5d5fd5c6f81efa40f5d10c四8bb200f805e679d633ee584748e5feef003e0921dea736ba91eef72f3d591d3a54cd59fd36f61140fdd3fb2e2c028b684e50cbeae4a1f386f6ab35359d46a29996c0f7d9a4a189f1096150496746f064c3cc四1cf111b0L  
d=invmod(e,(p-1)*(q-1))  
d&amp;((1&lt;&lt;512)-1)=0x17c四b18f1290b6a0886eaa7bf426485a3994c5b71186fe84d5138e18de7e060db57f9580381a917fdfd171bfd159825a7d1e2800e2774f5e4449d17e6723749bL</p>
<p><strong>解题脚本</strong></p>
<pre><code>def partial_p(p0, kbits, n):    
PR.&lt;x&gt; = PolynomialRing(Zmod(n))    
nbits = n.nbits()    
f = 2^kbits*x + p0    
f = f.monic()    
roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3)  # find root &lt; 2^(nbits//2-kbits) with factor &gt;= n^0.3    
if roots:    
x0 = roots[0]    
p = gcd(2^kbits*x0 + p0, n)    
return ZZ(p)


def find_p(d0, kbits, e, n):    
X = var('X')
for k in range(1, e+1):
results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)    
for x in results:    
p0 = ZZ(x[0])    
p = partial_p(p0, kbits, n)    
if p:    
return p


if __name__ == '__main__':  
# n(必须为整形才可计算) = 0x51fb3416aa0d71a430157d7c9853602a758e15462e7c08827b04cd3220c四27bbb8199ed4f5393dae43f013b68732a685defc17497f0912c886fa780dfacdfbb1461197d95a92a7a74ade874127a61411e14a901382ed3fb9d62c040c0dbaa374b5a4df06481a26da3fca271429ff10a4fc973b1c82553e3c1dd4f2f37dc24b3b
# d0=给出的部分d(必须为整形才可计算) = 0x17c四b18f1290b6a0886eaa7bf426485a3994c5b71186fe84d5138e18de7e060db57f9580381a917fdfd171bfd159825a7d1e2800e2774f5e4449d17e6723749b
e = 3  
n = 57569201048993475052349187244752169754165154575782760003851777813767048953051839288528137121670999884309849815765999616346303792471518639080697166767644957046582385785721102370288806038187956032505761532789716009522131450217010629338000241936036185205038814391205848232364006349213836317806903032515194407739  
nbits = n.nbits()  
kbits = floor(nbits*0.5)  
print(&quot;kbits : &quot;, kbits)
d0 = 1244848677959253796774387650148978357579294769878147704641867595620534030329181934099194560059806799908134954814673426128260540575360296026444649631806619  
print(&quot;lower %d bits (of %d bits) is given&quot; % (kbits, nbits))

p = find_p(d0, kbits, e, n)  
print(&quot;found p: %d&quot; % p)
q = n//p  
# print(d)
print(&quot;完整的d是:&quot;+str(inverse_mod(e, (p-1))))
</code></pre>
<p><strong>计算结果</strong></p>
<p>➜  RSA-and-LLL-attacks sage partial_key_exposure_attack.sage
kbits :  511
lower 511 bits (of 1023 bits) is given
found p: 7086179599191994333603836952445140343587486096628720220842297473373568276314821730585498733360983965734902690794828276489674036310720194369289757363461559
完整的d是:4724119732794662889069224634963426895724990731085813480561531648915712184209881153723665822240655977156601793863218850993116024207146796246193171575641039</p>
<h2 id="dp或dq泄漏攻击"><a class="header" href="#dp或dq泄漏攻击">dp或dq泄漏攻击</a></h2>
<h3 id="dpdq泄露"><a class="header" href="#dpdq泄露">dp&amp;dq泄露</a></h3>
<h4 id="可攻击特征-15"><a class="header" href="#可攻击特征-15">可攻击特征</a></h4>
<p>已知 p, q, dp, dq, c求m。</p>
<h4 id="原理-10"><a class="header" href="#原理-10">原理</a></h4>
<p>dp本来是为了加速rsa加解密效率的,不过由于dp和p的关系相当密切,所以当dp泄漏也有相当大的危害</p>
<p>dp=d%(p-1)
dq=d%(q-1)
dp<em>e = 1 mod(p-1)
dq</em>e = 1 mod(q-1)</p>
<h4 id="buuctf-rsa1"><a class="header" href="#buuctf-rsa1">BUUCTF-RSA1</a></h4>
<p><strong>题目</strong></p>
<p>p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852</p>
<p><strong>解题</strong></p>
<pre><code>#!/usr/bin/python2

import gmpy2 
from Crypto.Util.number import long_to_bytes

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

InvQ=gmpy2.invert(q,p) 
mp=pow(c,dp,p) 
mq=pow(c,dq,q) 
m=(((mp-mq)*InvQ)%p)*q+mq

print(long_to_bytes(m))
</code></pre>
<h3 id="dp泄露"><a class="header" href="#dp泄露">dp泄露</a></h3>
<h4 id="可攻击特征-16"><a class="header" href="#可攻击特征-16">可攻击特征</a></h4>
<p>题目给出公钥n,e以及dp，给出密文要求解明文，我们可以通过n，e，dp求解私钥d。</p>
<h4 id="原理-11"><a class="header" href="#原理-11">原理</a></h4>
<p>推导过程参考：https://blog.csdn.net/weixin_45369385/article/details/109208109</p>
<h4 id="wustctf2020-dp_leaking"><a class="header" href="#wustctf2020-dp_leaking">WUSTCTF2020-dp_leaking</a></h4>
<p><strong>题目</strong></p>
<p>e = 65537
n = 156808343598578774957375696815188980682166740609302831099696492068246337198792510898818496239166339015207305102101431634283168544492984586566799996471150252382144148257236707247267506165670877506370253127695314163987084076462560095456635833650720606337852199362362120808707925913897956527780930423574343287847
c = 108542078809057774666748066235473292495343753790443966020636060807418393737258696352569345621488958094856305865603100885838672591764072157183336139243588435583104423268921439473113244493821692560960443688048994557463526099985303667243623711454841573922233051289561865599722004107134302070301237345400354257869
dp = 734763139918837027274765680404546851353356952885439663987181004382601658386317353877499122276686150509151221546249750373865024485652349719427182780275825</p>
<p><strong>解题脚本</strong></p>
<pre><code>from gmpy2 import invert,powmod
from Crypto.Util.number import long_to_bytes

e = 65537
n = 156808343598578774957375696815188980682166740609302831099696492068246337198792510898818496239166339015207305102101431634283168544492984586566799996471150252382144148257236707247267506165670877506370253127695314163987084076462560095456635833650720606337852199362362120808707925913897956527780930423574343287847
c = 108542078809057774666748066235473292495343753790443966020636060807418393737258696352569345621488958094856305865603100885838672591764072157183336139243588435583104423268921439473113244493821692560960443688048994557463526099985303667243623711454841573922233051289561865599722004107134302070301237345400354257869
dp = 734763139918837027274765680404546851353356952885439663987181004382601658386317353877499122276686150509151221546249750373865024485652349719427182780275825

for x in range(1, e):
if (e * dp % x == 1):
p = (e * dp - 1) // x + 1
if (n % p != 0):
continue
q = n // p
phin = (p - 1) * (q - 1)
d = invert(e, phin)
m = powmod(c, d, n)
if (len(hex(m)[2:]) % 2 == 1):
continue

print(&quot;m:&quot;, m)
print(&quot;flag:&quot;, long_to_bytes(m))
</code></pre>
<h2 id="rsa-选择明密文攻击"><a class="header" href="#rsa-选择明密文攻击">RSA 选择明/密文攻击</a></h2>
<h3 id="选择明文攻击"><a class="header" href="#选择明文攻击">选择明文攻击</a></h3>
<h3 id="任意密文解密"><a class="header" href="#任意密文解密">任意密文解密</a></h3>
<h3 id="rsa-parity-oracle"><a class="header" href="#rsa-parity-oracle">RSA parity oracle</a></h3>
<h3 id="rsa-byte-oracle"><a class="header" href="#rsa-byte-oracle">RSA Byte Oracle</a></h3>
<h3 id="rsa-parity-oracle-variant"><a class="header" href="#rsa-parity-oracle-variant">RSA parity oracle variant</a></h3>
<h3 id="padding-attack"><a class="header" href="#padding-attack">Padding Attack</a></h3>
<h4 id="可攻击特征-17"><a class="header" href="#可攻击特征-17">可攻击特征</a></h4>
<p>加密的Padding可控。</p>
<h4 id="例题"><a class="header" href="#例题">例题</a></h4>
<p><strong>题目</strong></p>
<p>(‘n=’, ‘0xb33aebb1834845f959e05da639776d08a344abf098080dc5de04f4cbf4a1001dL’)
(‘e=’, ‘0x3’)
(‘c1=pow(hex_flag,e,n)’, ‘0x3aa5058306947ff46b0107b062d75cf9e497cdb1f120d02eaeca30f76492c550L’)
(‘c2=pow(hex_flag+1,e,n)’, ‘0x6a645739f25380a5e5b263ff5e5b4b9324381f6408a11fdaab0488209145fb3eL’)</p>
<p><strong>解题分析</strong></p>
<p>原理参考
https://www.anquanke.com/post/id/158944</p>
<p>意思很简单
1.pow(mm, e) != pow(mm, e, n)
2.利用rsa加密m+padding
值得注意的是，e=3，padding可控
那么我们拥有的条件只有
n,e,c,padding
所以这里的攻击肯定是要从可控的padding入手了</p>
<p><strong>解题脚本</strong></p>
<pre><code>import gmpy2
from Crypto.Util.number import long_to_bytes

def getM2(a,b,c1,c2,n,e):
a3 = pow(a,e,n)
b3 = pow(b,e,n)
first = c1-a3*c2+2*b3
first = first % n
second = e*b*(a3*c2-b3)
second = second % n
third = second*gmpy2.invert(first,n)
third = third % n
fourth = (third+b)*gmpy2.invert(a,n)
return fourth % n
e=0x3
a=1
b=-1
c1=0x3aa5058306947ff46b0107b062d75cf9e497cdb1f120d02eaeca30f76492c550
c2=0x6a645739f25380a5e5b263ff5e5b4b9324381f6408a11fdaab0488209145fb3e
padding2=1
n=0xb33aebb1834845f959e05da639776d08a344abf098080dc5de04f4cbf4a1001d
m = getM2(a,b,c1,c2,n,e)-padding2
print(long_to_bytes(m))
</code></pre>
<h3 id="rsa-lsb-oracle-attack"><a class="header" href="#rsa-lsb-oracle-attack">RSA LSB Oracle Attack</a></h3>
<h4 id="可攻击特征-18"><a class="header" href="#可攻击特征-18"><strong>可攻击特征</strong></a></h4>
<p>可以选择密文并泄露最低位。</p>
<p>参考博客https://www.sohu.com/a/243246344_472906</p>
<h4 id="原理-12"><a class="header" href="#原理-12"><strong>原理</strong></a></h4>
<p>在一次RSA加密中，明文为m，模数为n，加密指数为e，密文为c。 我们可以构造出c’=((2^e)c)%n=((2^e)(m^e))%n=((2m)^e)%n， 因为m的两倍可能大于n，所以经过解密得到的明文是 m’=(2m)%n 。 我们还能够知道 m’ 的最低位lsb 是1还是0。 因为n是奇数，而2m是偶数，所以如果lsb 是0，说明(2m)%n 是偶数，没有超过n，即m&lt;n/2.0，反之则m&gt;n/2.0 。 举个例子就能明白2%3=2 是偶数，而4%3=1 是奇数。 以此类推，构造密文c“=(4^e)c)%n 使其解密后为m“=(4m)%n ，判断m“ 的奇偶性可以知道m 和 n/4 的大小关系。 所以我们就有了一个二分算法，可以在对数时间内将m的范围逼近到一个足够狭窄的空间。</p>
<h4 id="攻击脚本-1"><a class="header" href="#攻击脚本-1"><strong>攻击脚本</strong></a></h4>
<pre><code>def brute_flag(encrypted_flag, n, e):

flag_count = n_count = 1
flag_lower_bound = 0
flag_upper_bound = n
ciphertext = encrypted_flag
mult = 1
while flag_upper_bound &gt; flag_lower_bound + 1:
sh.recvuntil(&quot;input your option:&quot;)
sh.sendline(&quot;D&quot;)
ciphertext = (ciphertext * pow(2, e, n)) % n
flag_count *= 2
n_count = n_count * 2 - 1

print(&quot;bit = %d&quot; % mult)
mult += 1


sh.recvuntil(&quot;Your encrypted message:&quot;)
sh.sendline(str(ciphertext))

data=sh.recvline()[:-1]
if(data=='The plain of your decrypted message is even!'):
flag_upper_bound = n * n_count / flag_count
else:
flag_lower_bound = n * n_count / flag_count
n_count += 1
return flag_upper_bound
</code></pre>
<h2 id="rsa-侧信道攻击"><a class="header" href="#rsa-侧信道攻击">RSA 侧信道攻击</a></h2>
<h2 id="bleichenbachers-attack"><a class="header" href="#bleichenbachers-attack">Bleichenbacher’s attack</a></h2>
<p>PKCS 1.5 标准中可以伪造 RSA 签名</p>
<p>http://ddaa.tw/gctf_crypto_201_rsa_ctf_challenge.html</p>
<h2 id="附1公钥私钥获取信息"><a class="header" href="#附1公钥私钥获取信息">附1:公钥私钥获取信息</a></h2>
<h3 id="openssl"><a class="header" href="#openssl">OpenSSL</a></h3>
<p>OpenSSL是开源的的软件库包，其支持许多不同的加密算法。当然了其中有许多实用的工具，我们这里就使用其中有关RSA的部分。</p>
<h4 id="openssl-genrsa"><a class="header" href="#openssl-genrsa">openssl genrsa</a></h4>
<p>该命令生成一个RSA私钥。</p>
<p>➜  ~ openssl genrsa -h
usage: genrsa [args] [numbits]    //密钥位数，建议在 2048bit 以上
-des            encrypt the generated key with DES in cbc mode
-des3           encrypt the generated key with DES in ede cbc mode (168 bit key)
-aes128, -aes192, -aes256    encrypt PEM output with cbc aes
-camellia128, -camellia192, -camellia256    encrypt PEM output with cbc camellia
-out file       输出key到file    //公钥可以从该私钥file中提取
-passout arg    output file pass phrase source
-f4             use F4 (0x10001) for the E value
-3              use 3 for the E value</p>
<h4 id="openssl-rsa"><a class="header" href="#openssl-rsa">openssl rsa</a></h4>
<p>处理RSA密钥的格式转换等问题。</p>
<p>➜  ~ openssl rsa -h
Invalid cipher ‘h’
usage: rsa [-ciphername] [-check] [-in file] [-inform fmt]
[-modulus] [-noout] [-out file] [-outform fmt] [-passin src]
[-passout src] [-pubin] [-pubout] [-sgckey] [-text]</p>
<p>-check             Check consistency of RSA private key           # 检查输入密钥的正确性和一致性
-in file           Input file (default stdin)
-inform format     Input format (DER, NET or PEM (default))       # 输入文件格式，默认pem
-modulus           Print the RSA key modulus      # 输出模数
-noout             Do not print encoded version of the key
-out file          Output file (default stdout)
-outform format    Output format (DER, NET or PEM (default PEM))  # 输出文件格式，默认pem
-passin src        Input file passphrase source   # 指定输入文件的加密口令，可来自文件、终端、环境变量等
-passout src       Output file passphrase source
-pubin             Expect a public key (default private key)      # 指定输入文件是公钥
-pubout            Output a public key (default private key)
-sgckey            Use modified NET algorithm for IIS and SGC keys
-text              Print in plain text in addition to encoded</p>
<h4 id="openssl-rsautl"><a class="header" href="#openssl-rsautl">openssl rsautl</a></h4>
<p>使用RSA密钥进行加密、解密、签名和验证等运算。</p>
<div class="table-wrapper"><table><thead><tr><th>数据补齐方式</th><th>输入数据长度</th><th>输出数据长度</th><th>参数字符串</th></tr></thead><tbody>
<tr><td>PKCS#1 v1.5</td><td>少于(密钥长度-11)字节</td><td>同密钥长度</td><td>-pkcs</td></tr>
<tr><td>PKCS#1 OAEP</td><td>少于(密钥长度-11)字节</td><td>同密钥长度</td><td>-oaep</td></tr>
<tr><td>PKCS#1 for SSLv23</td><td>少于(密钥长度-11)字节</td><td>同密钥长度</td><td>-ssl</td></tr>
<tr><td>不使用补齐</td><td>同密钥长度</td><td>同密钥长度</td><td>-raw</td></tr>
</tbody></table>
</div>
<p>➜  ~ openssl rsautl -h
Usage: rsautl [options]
-in file        input file
-out file       output file
-inkey file     input key
-keyform arg    private key format - default PEM   # 指定密钥格式
-pubin          input is an RSA public
-certin         input is a certificate carrying an RSA public key   # 指定输入的是证书文件
-ssl            use SSL v2 padding                 # 使用SSLv23的填充方式
-raw            use no padding                     # 不进行填充
-pkcs           use PKCS#1 v1.5 padding (default)  
-oaep           use PKCS#1 OAEP
-sign           sign with private key              # 使用私钥做签名
-verify         verify with public key             # 使用公钥认证签名
-encrypt        encrypt with public key            # 使用公钥加密
-decrypt        decrypt with private key           # 使用私钥解密</p>
<h4 id="openssl-加解密实例"><a class="header" href="#openssl-加解密实例">openssl 加解密实例</a></h4>
<p>生成私钥:<code>openssl genrsa -out prikey.pem</code></p>
<p>查看私钥:<code>openssl rsa -in prikey.pem -text -modulus</code></p>
<p>从私钥总提取公钥:<code>openssl rsa -in prikey.pem -pubout -out pubkey.pem</code></p>
<p>查看公钥:<code>openssl rsa -in pubkey.pem -text -modulus -pubin</code></p>
<p>加密:<code>openssl rsautl -encrypt -in file.plain -inkey pubkey.pem -pubin -out file.enc</code></p>
<p>解密:(如有对应的补齐方式需要指定):<code>rsautl -decrypt -inkey prikey -in filename</code></p>
<h3 id="其他工具"><a class="header" href="#其他工具">其他工具</a></h3>
<h4 id="rsatools"><a class="header" href="#rsatools">rsatools</a></h4>
<p>使用使用p,q,e生成pem文件：<code>python rsatools.py -p p参数 -q q参数 -e e的值 -o prikey.pem</code></p>
<h4 id="rsactftool"><a class="header" href="#rsactftool">RsaCtfTool</a></h4>
<p>查看公钥的一些信息:<code>./RsaCtfTool.py --dumpkey --key ./key.pub</code></p>
<p>已知公钥求私钥:<code>./RsaCtfTool.py --publickey ./key.pub --private</code></p>
<p>已知公钥，自动解密:<code>./RsaCtfTool.py --publickey ./key.pub --uncipherfile filename</code></p>
<p>已知 $n,e$ 生成公钥:<code>./RsaCtfTool.py --createpub -n 7828374823761928712873129873981723...12837182 -e 65537</code></p>
<p>更多参看：https://github.com/Ganapati/RsaCtfTool</p>
<h4 id="2020西湖论剑-rsa-brokensystems"><a class="header" href="#2020西湖论剑-rsa-brokensystems">2020西湖论剑-RSA-BrokenSystems</a></h4>
<p><strong>题目</strong></p>
<p>给了两个文件，message 和 public.key，还有一个脚本如下：</p>
<pre><code class="language-python">from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from secret import flag
import os
rsa = RSA.generate(2048)
public_key = rsa.publickey().exportKey()
f=open(&quot;public.key&quot;,&quot;w&quot;)
f.write(public_key.decode())
f.close()

rsakey=RSA.importKey(open(&quot;public.key&quot;,&quot;r&quot;).read())
rsa = PKCS1_OAEP.new(rsakey)
msg=rsa.encrypt(flag.encode())
f=open(&quot;message&quot;,&quot;wb&quot;)
f.write(msg)
f.close()
</code></pre>
<p><strong>解题思路</strong></p>
<p>首先我们看一下公钥的一些参数：</p>
<pre><code class="language-bash">python RsaCtfTool.py --dumpkey --key ./2020ctf-BrokenSystems/public.key
private argument is not set, the private key will not be displayed, even if recovered.
n: 24493816160588971749455534346389861269947121809901305744877671102517333076424951483888863597563544011725032585417200878377314372325231470164799594965293350352923195632229495874587039720317200655351788887974047948082357232348155828924230567816817425104960545706688263839042183224681231800805037117758927837949941052360649778743187012198508745207332696876463490071925421229447425456903529626946628855874075846839745388326224970202749994059533831664092151570836853681204646481502222112116971464211748086292930029540995987019610460396057955900244074999111267618452967579699626655472948383601391620012180211885979095636919
e: 3683191938452247871641914583009119792552938079110383367782698429399084083048335018186915282465581498846777124014232879019914546010406868697694661244001972931366227108140590201194336470785929194895915077935083045957890179080332615291089360169761324533970721460473221959270664692795701362942487885620152952927112838769014944652059440137350285198702402612151501564899791870051001152984815689187374906618917967106000628810361686645504356294175173529719443860140795170776862320812544438211122891112138748710073230404456268507750721647637959502454394140328030018450883598342764577147457231373121223878829298942493059211583
</code></pre>
<p>可以看到这里边的e特别大，大家都说是用Wiener攻击可以解出，我还没尝试，想用RsaCtfTool试试看，所以小结下，本题有两种解法：</p>
<ul>
<li>常规思路解d –&gt; 生成密钥key –&gt; 解密</li>
<li>使用RsaCtfTool工具suoha</li>
</ul>
<p><strong>解题</strong></p>
<p>使用RsaCtfTool爆破，我们可以看出该脚本最终用boneh_durfee爆破出了结果</p>
<pre><code>python RsaCtfTool.py --publickey ./2020ctf-BrokenSystems/public.key --private

[*] Testing key ./2020ctf-BrokenSystems/public.key.
...省略暴力尝试的一部分内容...
[*] Performing roca attack on ./2020ctf-BrokenSystems/public.key.
[*] Performing pollard_p_1 attack on ./2020ctf-BrokenSystems/public.key.
[*] Performing boneh_durfee attack on ./2020ctf-BrokenSystems/public.key.

Results for ./2020ctf-BrokenSystems/public.key:

Private key :
-----BEGIN RSA PRIVATE KEY-----
MIIEXgIBAAKCAQEAwgdFIj/1uUss2EEhZvcoiiHyGH4aQhRTkYyrA8gCU0USM+sb
3CNjdEIoqoaUqMLLyDP4Dd9AgxpokBsjC四Pz8P7Uty0LlCteld7ayNzABHoq+5DI
...篇幅过长省略...
UWAvuuxI7lGac2B+/A/EcwBJfOT/qLCPpvFhA0Qje1HqlNSXc9e/FGt1UwxZkJBJ
JNGhlKRKaB0RJgJW5dA1jfyYU8xpPsDxfdDzLf2y167IbfqNNmL7ZF8IHj5+hPsB
0oVAN0gvoLxcOM2qMOXIt6aM
-----END RSA PRIVATE KEY-----
</code></pre>
<p>获得Private Key后，我们将该密钥保存为<code>pri.key</code>，使用openssl解出结果，需要注意的是解密时要指定填充模式为<code>PKCS1_OAEP</code></p>
<pre><code>cd 2020ctf-BrokenSystems &amp;&amp; openssl rsautl -decrypt -oaep -in message -inkey pri.key
DASCTF{ce02347b86167f2d3519251b9a8a5ba8}
</code></pre>
<h3 id="rsa私钥文件修复"><a class="header" href="#rsa私钥文件修复">RSA私钥文件修复</a></h3>
<p>私钥文件修复可参考该帖子：https://code.felinae98.cn/CTF/Crypto/RSA-%E7%A7%81%E9%92%A5%E9%87%8D%E6%9E%84/</p>
<pre><code class="language-python">#!/usr/bin/python3

import re
from itertools import product
from Crypto.Util.number import GCD, inverse


def solve_linear(a, b, mod):
    if a &amp; 1 == 0 or b &amp; 1 == 0:
        return None
    return (b * inverse(a, mod)) &amp; (mod - 1)  # 计算b*a^(-1)%mod


def to_n(s):
    s = re.sub(r&quot;[^0-9a-f]&quot;, &quot;&quot;, s)
    return int(s, 16)


def msk(s):
    cleaned = &quot;&quot;.join(map(lambda x: x[-2:], s.split(&quot;:&quot;)))   #去掉冒号和多余字符和空格
    return msk_ranges(cleaned), msk_mask(cleaned), msk_val(cleaned)


def msk_ranges(s):      #    求每一个半字节的取值范围
    return [range(16) if c == &quot; &quot; else [int(c, 16)] for c in s]


def msk_mask(s):
    return int(&quot;&quot;.join(&quot;0&quot; if c == &quot; &quot; else &quot;f&quot; for c in s), 16)


def msk_val(s):
    return int(&quot;&quot;.join(&quot;0&quot; if c == &quot; &quot; else c for c in s), 16)


N = to_n(&quot;&quot;&quot;\
00:c0:97:78:53:45:64:84:7d:8c:c4:b4:20:e9:33:
58:67:ec:78:3e:6c:f5:f0:5c:a0:3e:ee:dc:25:63:
d0:eb:2a:9e:ba:8f:19:52:a2:67:0b:e7:6e:b2:34:
b8:6d:50:76:e0:6a:d1:03:cf:77:33:d8:b1:e9:d7:
3b:e5:eb:1c:65:0c:25:96:fd:96:20:b9:7a:de:1d:
bf:fd:f2:b6:bf:81:3e:3e:47:44:43:98:bf:65:2f:
67:7e:27:75:f9:56:47:ba:c4:f0:4e:67:2b:da:e0:
1a:77:14:40:29:c1:a8:67:5a:8f:f5:2e:be:8e:82:
31:3d:43:26:d4:97:86:29:15:14:a9:69:36:2c:76:
ed:b5:90:eb:ec:6f:ce:d5:ca:24:1c:aa:f6:63:f8:
06:a2:62:cb:26:74:d3:5b:82:4b:b6:d5:e0:49:32:
7b:62:f8:05:c4:f7:0e:86:59:9b:f3:17:25:02:aa:
3c:97:78:84:7b:16:fd:1a:f5:67:cf:03:17:97:d0:
c6:69:85:f0:8d:fa:ce:ee:68:24:63:06:24:e1:e4:
4c:f8:e9:ad:25:c7:e0:c0:15:bb:b4:67:48:90:03:
9b:20:7f:0c:17:eb:9d:13:44:ab:ab:08:a5:c3:dc:
c1:98:88:c5:ce:4f:5a:87:9b:0b:bf:bd:d7:0e:a9:
09:59:81:fa:88:4f:59:60:6b:84:84:ad:d9:c7:25:
8c:e8:c0:e8:f7:26:9e:37:95:7c:e1:48:29:0f:51:
e7:bd:98:2f:f6:cc:80:e7:f0:32:0b:89:51:92:4e:
c2:6d:50:53:2b:3b:77:72:d1:bd:1a:1f:92:d7:12:
79:61:61:c5:a4:7e:b3:85:eb:f0:7c:6d:46:03:c5:
e6:d5:81:2c:ba:7e:ea:8d:51:7d:63:55:34:2a:b6:
d4:dc:31:5a:f1:99:e3:dc:8c:83:0b:a2:2a:d5:3c:
41:48:41:54:1a:a9:e8:b6:70:bf:d3:fe:ed:19:17:
14:94:13:b3:17:e3:8b:8e:6f:53:ed:e2:44:e8:4a:
32:d6:5c:0d:a8:80:f5:fc:02:e9:46:55:d5:a4:d3:
e7:c6:30:77:f9:73:e9:44:52:d8:13:9d:5d:bf:9e:
fa:3a:b5:96:79:82:5b:cd:19:5c:06:a9:00:96:fd:
4c:a4:73:88:1a:ec:3c:11:de:b9:3d:e0:50:00:1e:
ac:21:97:a1:96:7d:6b:15:f9:6c:c9:34:7f:70:d7:
9d:2d:d1:48:4a:81:71:f8:12:dd:32:ba:64:31:60:
08:26:4b:09:22:03:83:90:17:7f:f3:a7:72:57:bf:
89:6d:e4:d7:40:24:8b:7b:bd:df:33:c0:ff:30:2e:
e8:6c:1d&quot;&quot;&quot;)

p_ranges, pmask_msk, pmask_val = msk(&quot;&quot;&quot;\
 0: e:  :  :  :c :c :  :  :  :b :  :  :  :  :
  :ab: e: 2: 8:c :  :  : 1:6 :6 : 6: f:d9: 0:
8 :5c:7 :06:  :  :  :0 : 3:5 :4b:  :6 :  :  :
2 :  :6 :  :  :  :2 :bc: c:  :85:1 : 1:d : 3:
 1:b4:  : b: 1: 3: d:a :  :  :6e: 0:b :2 :  :
  :b :  :9 :e :  :82:8d:  :  :13:  :  : a: a:
  :  :4 :  :c : f:  :  :7 :e :0a:  :  : b: 5:
  : e:91:3 :  :3c: 9:  : 6:  :  :b5:7d: 1:  :
  :  :  :b :a1:99:6 :4 :3 :c :1a:02:4 :  : 9:
9 :f : d:bd:  :0 :  :  :  :b3:  : 4:  :e9: 9:
  : d:  :  :7 :  :93:  : e:dc:  : 0:  :e7:  :
e :  :2 : b: 2:5 :  :  :  :  : c:5f:  :  :e2:
  :  : 9:  :2a:  : e:  :  :2 :  :9f: 7:3 :  :
b : f:b :  : 8: 7:  :  :f :6 :e :c :  :3 :  :
f7: 5: 8: 5:  :  :  :  :  : 8: e:  :03: c:  :
33:76:e : 1:7 : c:  : 0:  :0b:  : a:  : 2: 9:
  :c8:bf:  :  :06: 7:d5:  :02: c:b :e2: 7:2 :
  :  &quot;&quot;&quot;)

q_ranges, qmask_msk, qmask_val = msk(&quot;&quot;&quot;\
 0: f:  :d0: 1:55: 4:31:  : b:c4:8 :  : e: d:
34: 3:f :  :  :  :  : 8:99:1 :  : a:0 :  :4 :
0 :  :f :  :a4:41:2 :  :a :  : 1:  : a: c:  :
  :  : 9:  :  : 2:f4: f:  :  :  :  :1 : 4:9 :
a :  :  :79:0 :  :  :  :  : 2: 8:b :  :4 : 8:
  :9b: 1:  :d :  :f :e4:  :4 :c :e :  :3 :  :
 7:2 :  :d :8 :2 :7 :  :d :67:fc:e : 0:f9: 7:
8 :  :  :  :1 :2f:  :51:  :  :2e:0a: e:3d: 6:
b :  :dd:  : 0:fb:  :f4:  :  :  :b4: 9:c :  :
 a:  :  :  :d :  :  :6b: 2:  :9b: a:60:  :d6:
 0:4f:16:d1:  :  :5 :fc:  :f :  :8 :  :  :  :
 1: 6:e1:9 : e:4 : 6: c: d:d :73: 3:  :  :7 :
  :8 : 9:  :3b:f : 2:  :  :f1: e:  :  :1e:  :
8 :  :  : 6:0 : 4:99:e :  : 5:  :  : 4:  :  :
  : a:81:64:  :7 :f : 9: d:  :9 :  : 7:93:f :
ac:8c:  : 8:  : 0: d: 8:  :7 :  :1d:  :f :  :
1 :a :6 :8 :  :60:  :b3:  :  :  :89:  :  :14:
  :5 &quot;&quot;&quot;)


_, dmask_msk, dmask_val = msk(&quot;&quot;&quot;\
  :  :  : f:8 :a5:d : 2: 0:b :7 :  : 1:  : 4:
 1:0d:  :3 :  :6 :  :  : b:  :  :  :e :  :  :
0e: 0:db:  :1a:1c:c0:  : e:  :  :99:bc:8 :a5:
7 :7 :7 : b:  :  : 8: 8:  :7 :55: 2:  :  :f :
b2:  :  :b :f :4 :  : 8:  :b :  :  :  : 0:  :
0 :  :6 :9 :  :  :  : b: 4:  : 0: a: 5:07:b :
 9: c:9a: 9:  : 7:9e:  : b:60:f :  :  :  :0 :
  : 3:0 :  :  :  : 1:b :  :  : b: 6:0 :f :  :
  : 2:18: 6: b:1 :  :  :  :  :d3:f3:  :a :  :
 3:  :  :  :  : 3: d: 1: 2:7 :  : d:  : 2: d:
  :  : d:4 :  :d :  :6d: c:a :b6:  :  :  : 1:
69:  : 7:  :89:  :c :8 :61: d:25: 3:7 :1b: 4:
b :  :8 :55:  :49: 1:2 :3 :  :1 :e9:a8: 3:  :
9 :  : 1:f8:d3:  :e :  :d :  :9 :b6:  :  :71:
1 :  :c1:  : b: 1:  : 6:e :  :64:  :  :1a:c :
  : b:  :bf:c :  : 0:  : 8:a :4 :  :26:a :5 :
6 :  :  :  :eb:  :e5: a:  :3e:f9:10:0 :  :  :
 6:0 :  : 8:  : 1:72: c:0 : f:5 : f:9c: 0: e:
 7:b :  :  :  :  :d9: 4:  : e:c :68:  :  :  :
 c:  :3a:  :  :a0:ea: 3: 4:  :72:a :d : 8:  :
  :0d:5 :0 : a: 7:c :bb: 6: 4:a :ce:d :2 : 1:
  :  :17:6 :  : c: b:  : f:  :3 : 5:6 :3 :0e:
  : 7:c :3e: 2: 9: 7: 6: f: e: f: 9:  :f3: 9:
a :c1:6 :  : 1:9 :  :43:  : f: 5:  :0 :27: 4:
4 :a :  :e9:  : 8: 4:3 :8a: 6:16:d5:c : e: e:
  :d : c:b :a8:  : 7:  : 9:  :7 :7d:  :  :  :
  :  :  :4 :2 :  : 3: 3: 6:  :  :  :7b:0 :  :
 e:  :0 :  :a :  : 5:  :  :  : 5:1 :82:c :0d:
4 :2 :fd:36: 5:50:0 :  :  :d : f: 6:  :  :e :
0 :  :  :ce:  :9e:8 :  :0 :d :07:b3:  :  :  :
0 :e4:  :  :68:b :c :  : c:5 :  :  :3 : 7: 2:
 c:e0:  :5 :  :  :b4:  :ef: 7:  :1 :e : 0:f :
  :6 :  :  :  :e0:c :3 :  :  : 3:  : d:  :  :
 3: 3: c: a:  :b : a:71: 3: 0:a :  :4 :5d:  :
0 :4 &quot;&quot;&quot;)


_, dpmask_msk, dpmask_val = msk(&quot;&quot;&quot;\
  : 3:2a:  : d:  :  :  :  :0 :1 : f:  :  : 6:
1 :2 :1b:07: a:e :b :c5:58:7 :  :e8: 7: 1: c:
  : 1:b :a0: 4:0f:5 :67:  :3 :7 :6 :f9:  : c:
  :79: 0:1 :65:  :8 :  :99: d:d :  :2 :9 :0 :
 e:  :0 :  :  :  : d:  :d :7 :6 :a9: a:8b: b:
  :  : 7: a:37:  :  :7 :1 :6 :  :c2: 7:6 :b :
 e:  :  :  :  :  :  :b :3a:5 :  :  :  :  :  :
  :  :  :cd:8 :  : d:  :7 : 3:  : f:e : c:  :
  : a:  :c : f:c : 7:b :5 :  :  :2 :8 :8 :6 :
0a: a:  :  :3 :db:  : 4:00:  : d:  :b : 5:  :
20: 2: 5:  :82:  : 0: 6:  :8a:  :7 :  : 8:  :
 4: 1:  :  :  : 8:46:  :  :  :  :  : 0:f :c8:
2 :  : c:7 :  : 1:  :  :2 : 0: 5:  :  : 1:9b:
 6:9 : 0:74:  :c :  :e :  :  :cb:b :3 :3 :  :
 2:  :  :47:  :2 : 0:5 :  :  : d: 6:83:  :  :
  :c7:  :  :0b:  :  : c:  :3 :8 :  :9 :4 : 7:
5 :c0:fe:  :f9: 1:  :0 : e: 8:02:  : f:  :c :
55:61&quot;&quot;&quot;)

_, dqmask_msk, dqmask_val = msk(&quot;&quot;&quot;\
  :0b:7 :4 :0 : 0:6 : 7:7e:  : 5:  : 7:  : a:
a :d : 0: 6: 4:86:  :  :8 :  :  :  :  :e :8f:
 9:  :  :  : 1:  :2 :  : 7: b:1 :5 : f:  :8 :
  :d :21:  :e : d:  :c9:e : b:  :  :1 :  :  :
  :d :a2:b7:  :  :  :f3:  :42:  :e : c:  :f :
  : 0:f :7 : 4: 5:34:  :4 : c:  :  :8 :d : 8:
5 :af: 3:1d: 5:4 :  :2 :  :6 :c : 6:a :1 :5 :
 a:9 :  :d :  :  :0a:a1:  :f :7 :9 :b :  :  :
 f:2 :27: f:  :0 :f6:4d:  :  :  :  :  :5 :  :
 4:08:  : 5:  : 8: 5:  :  :  :18: 4: 8:57: 2:
 f: a:  :  :a8: f: c:f : e: 1:9 :c : 4:9 :  :
  :  :  :  :  : 1:  :2 :  :d1:  : 6:e : d:  :
  : f:04:2 :8d:  : 3:  :  :b : 8:  :d6:  : 2:
  :  :  :6 :  : f:  :  : 0:6 :  :51:  :48:19:
  :  :  :69:4 : c:  :c :  : f:  :f4:d :  : f:
 d:0 :0d:b :3 : 3:2 :  :  :6 : b:5 :2 :  : c:
 1:5a: f:f :  :  :7e:3e:  :d :f :0 : d: c: 6:
 1&quot;&quot;&quot;)


E = 0x10001

def search(K, Kp, Kq, check_level, break_step):
    max_step = 0
    cands = [0] # 广搜队列
    for step in range(1, break_step + 1):
        # step代表复原倒数第step步
        max_step = max(step, max_step)

        mod = 1 &lt;&lt; (4 * step)
        mask = mod - 1

        cands_next = []
        for p, new_digit in product(cands, p_ranges[-step]):
            pval = (new_digit &lt;&lt; ((step - 1) * 4)) | p

            # 四个剪枝
            if check_level &gt;= 1:
                qval = solve_linear(pval, N &amp; mask, mod)
                if qval is None or not check_val(qval, mask, qmask_msk, qmask_val):
                    continue

            if check_level &gt;= 2:
                val = solve_linear(E, 1 + K * (N - pval - qval + 1), mod)
                if val is None or not check_val(val, mask, dmask_msk, dmask_val):
                    continue

            if check_level &gt;= 3:
                val = solve_linear(E, 1 + Kp * (pval - 1), mod)
                if val is None or not check_val(val, mask, dpmask_msk, dpmask_val):
                    continue

            if check_level &gt;= 4:
                val = solve_linear(E, 1 + Kq * (qval - 1), mod)
                if val is None or not check_val(val, mask, dqmask_msk, dqmask_val):
                    continue

                if pval * qval == N: #得到答案
                    print(&quot;Kq =&quot;, Kq)
                    print(&quot;pwned&quot;)
                    print(&quot;p =&quot;, pval)
                    print(&quot;q =&quot;, qval)
                    p = pval
                    q = qval
                    d = inverse(E, (p - 1) * (q - 1))
                    print(&quot;d =&quot;, d)
                    coef = inverse(p, q)

                    from Crypto.PublicKey import RSA
                    print(RSA.construct((N, E, d, p, q, coef)).exportKey().decode())
                    quit()

            cands_next.append(pval)

        if not cands_next:
            return False
        cands = cands_next
    return True


def check_val(val, mask, mask_msk, mask_val):
    test_mask = mask_msk &amp; mask
    test_val = mask_val &amp; mask
    return val &amp; test_mask == test_val



for K in range(1, E):
    if K % 100 == 0:
        print(&quot;checking&quot;, K)
    if search(K, 0, 0, check_level=2, break_step=20):
        print(&quot;K =&quot;, K)
        break

for Kp in range(1, E):
    if Kp % 1000 == 0:
        print(&quot;checking&quot;, Kp)
    if search(K, Kp, 0, check_level=3, break_step=30):
        print(&quot;Kp =&quot;, Kp)
        break

for Kq in range(1, E):
    if Kq % 100 == 0:
        print(&quot;checking&quot;, Kq)
    if search(K, Kp, Kq, check_level=4, break_step=9999):
        print(&quot;Kq =&quot;, Kq)
        break
</code></pre>
<pre><code class="language-sh">openssl rsautl -decrypt -inkey private.pem -keyform PEM -in flag.enc -oaep
</code></pre>
<p><strong>题目</strong></p>
<h3 id="rsa-私钥恢复和最优非对称加密填充jarvis-oj-god-like-rsa"><a class="header" href="#rsa-私钥恢复和最优非对称加密填充jarvis-oj-god-like-rsa">RSA 私钥恢复和最优非对称加密填充(Jarvis OJ-God Like RSA)</a></h3>
<p>题目给出了三个文件，加密后的 flag<code>flag.enc</code>，残缺的私钥<code>private.corrupted</code>，公钥<code>pubkey.pem</code></p>
<p><a href="https://gitcode.net/dnrops/rsa_ctf_problems/-/raw/master/godlikeRSA.rar">godlikeRSA</a>
解题可参考：<a href="https://www.40huo.cn/blog/rsa-private-key-recovery-and-oaep.html">https://www.40huo.cn/blog/rsa-private-key-recovery-and-oaep.html</a></p>
<pre><code class="language-python">import re
import pickle
from itertools import product
from libnum import invmod, gcd
from Crypto.PublicKey import RSA


def solve_linear(a, b, mod):
    if a &amp; 1 == 0 or b &amp; 1 == 0:
        return None
    return (b * invmod(a, mod)) &amp; (mod - 1)  # hack for mod = power of 2


def to_n(s):
    s = re.sub(r&quot;[^0-9a-f]&quot;, &quot;&quot;, s)
    return int(s, 16)


def msk(s):
    cleaned = &quot;&quot;.join(map(lambda x: x[-2:], s.split(&quot;:&quot;)))
    return msk_ranges(cleaned), msk_mask(cleaned), msk_val(cleaned)


def msk_ranges(s):
    return [range(16) if c == &quot; &quot; else [int(c, 16)] for c in s]


def msk_mask(s):
    return int(&quot;&quot;.join(&quot;0&quot; if c == &quot; &quot; else &quot;f&quot; for c in s), 16)


def msk_val(s):
    return int(&quot;&quot;.join(&quot;0&quot; if c == &quot; &quot; else c for c in s), 16)


E = 65537

N = to_n(&quot;&quot;&quot;00:c0:97:78:53:45:64:84:7d:8c:c4:b4:20:e9:33:
    58:67:ec:78:3e:6c:f5:f0:5c:a0:3e:ee:dc:25:63:
    d0:eb:2a:9e:ba:8f:19:52:a2:67:0b:e7:6e:b2:34:
    b8:6d:50:76:e0:6a:d1:03:cf:77:33:d8:b1:e9:d7:
    3b:e5:eb:1c:65:0c:25:96:fd:96:20:b9:7a:de:1d:
    bf:fd:f2:b6:bf:81:3e:3e:47:44:43:98:bf:65:2f:
    67:7e:27:75:f9:56:47:ba:c4:f0:4e:67:2b:da:e0:
    1a:77:14:40:29:c1:a8:67:5a:8f:f5:2e:be:8e:82:
    31:3d:43:26:d4:97:86:29:15:14:a9:69:36:2c:76:
    ed:b5:90:eb:ec:6f:ce:d5:ca:24:1c:aa:f6:63:f8:
    06:a2:62:cb:26:74:d3:5b:82:4b:b6:d5:e0:49:32:
    7b:62:f8:05:c4:f7:0e:86:59:9b:f3:17:25:02:aa:
    3c:97:78:84:7b:16:fd:1a:f5:67:cf:03:17:97:d0:
    c6:69:85:f0:8d:fa:ce:ee:68:24:63:06:24:e1:e4:
    4c:f8:e9:ad:25:c7:e0:c0:15:bb:b4:67:48:90:03:
    9b:20:7f:0c:17:eb:9d:13:44:ab:ab:08:a5:c3:dc:
    c1:98:88:c5:ce:4f:5a:87:9b:0b:bf:bd:d7:0e:a9:
    09:59:81:fa:88:4f:59:60:6b:84:84:ad:d9:c7:25:
    8c:e8:c0:e8:f7:26:9e:37:95:7c:e1:48:29:0f:51:
    e7:bd:98:2f:f6:cc:80:e7:f0:32:0b:89:51:92:4e:
    c2:6d:50:53:2b:3b:77:72:d1:bd:1a:1f:92:d7:12:
    79:61:61:c5:a4:7e:b3:85:eb:f0:7c:6d:46:03:c5:
    e6:d5:81:2c:ba:7e:ea:8d:51:7d:63:55:34:2a:b6:
    d4:dc:31:5a:f1:99:e3:dc:8c:83:0b:a2:2a:d5:3c:
    41:48:41:54:1a:a9:e8:b6:70:bf:d3:fe:ed:19:17:
    14:94:13:b3:17:e3:8b:8e:6f:53:ed:e2:44:e8:4a:
    32:d6:5c:0d:a8:80:f5:fc:02:e9:46:55:d5:a4:d3:
    e7:c6:30:77:f9:73:e9:44:52:d8:13:9d:5d:bf:9e:
    fa:3a:b5:96:79:82:5b:cd:19:5c:06:a9:00:96:fd:
    4c:a4:73:88:1a:ec:3c:11:de:b9:3d:e0:50:00:1e:
    ac:21:97:a1:96:7d:6b:15:f9:6c:c9:34:7f:70:d7:
    9d:2d:d1:48:4a:81:71:f8:12:dd:32:ba:64:31:60:
    08:26:4b:09:22:03:83:90:17:7f:f3:a7:72:57:bf:
    89:6d:e4:d7:40:24:8b:7b:bd:df:33:c0:ff:30:2e:
    e8:6c:1d&quot;&quot;&quot;)

p_ranges, pmask_msk, pmask_val = msk(&quot;&quot;&quot; 0: e:  :  :  :c :c :  :  :  :b :  :  :  :  :
      :ab: e: 2: 8:c :  :  : 1:6 :6 : 6: f:d9: 0:
    8 :5c:7 :06:  :  :  :0 : 3:5 :4b:  :6 :  :  :
    2 :  :6 :  :  :  :2 :bc: c:  :85:1 : 1:d : 3:
     1:b4:  : b: 1: 3: d:a :  :  :6e: 0:b :2 :  :
      :b :  :9 :e :  :82:8d:  :  :13:  :  : a: a:
      :  :4 :  :c : f:  :  :7 :e :0a:  :  : b: 5:
      : e:91:3 :  :3c: 9:  : 6:  :  :b5:7d: 1:  :
      :  :  :b :a1:99:6 :4 :3 :c :1a:02:4 :  : 9:
    9 :f : d:bd:  :0 :  :  :  :b3:  : 4:  :e9: 9:
      : d:  :  :7 :  :93:  : e:dc:  : 0:  :e7:  :
    e :  :2 : b: 2:5 :  :  :  :  : c:5f:  :  :e2:
      :  : 9:  :2a:  : e:  :  :2 :  :9f: 7:3 :  :
    b : f:b :  : 8: 7:  :  :f :6 :e :c :  :3 :  :
    f7: 5: 8: 5:  :  :  :  :  : 8: e:  :03: c:  :
    33:76:e : 1:7 : c:  : 0:  :0b:  : a:  : 2: 9:
      :c8:bf:  :  :06: 7:d5:  :02: c:b :e2: 7:2 :
      :  &quot;&quot;&quot;)

q_ranges, qmask_msk, qmask_val = msk(&quot;&quot;&quot; 0: f:  :d0: 1:55: 4:31:  : b:c4:8 :  : e: d:
    34: 3:f :  :  :  :  : 8:99:1 :  : a:0 :  :4 :
    0 :  :f :  :a4:41:2 :  :a :  : 1:  : a: c:  :
      :  : 9:  :  : 2:f4: f:  :  :  :  :1 : 4:9 :
    a :  :  :79:0 :  :  :  :  : 2: 8:b :  :4 : 8:
      :9b: 1:  :d :  :f :e4:  :4 :c :e :  :3 :  :
     7:2 :  :d :8 :2 :7 :  :d :67:fc:e : 0:f9: 7:
    8 :  :  :  :1 :2f:  :51:  :  :2e:0a: e:3d: 6:
    b :  :dd:  : 0:fb:  :f4:  :  :  :b4: 9:c :  :
     a:  :  :  :d :  :  :6b: 2:  :9b: a:60:  :d6:
     0:4f:16:d1:  :  :5 :fc:  :f :  :8 :  :  :  :
     1: 6:e1:9 : e:4 : 6: c: d:d :73: 3:  :  :7 :
      :8 : 9:  :3b:f : 2:  :  :f1: e:  :  :1e:  :
    8 :  :  : 6:0 : 4:99:e :  : 5:  :  : 4:  :  :
      : a:81:64:  :7 :f : 9: d:  :9 :  : 7:93:f :
    ac:8c:  : 8:  : 0: d: 8:  :7 :  :1d:  :f :  :
    1 :a :6 :8 :  :60:  :b3:  :  :  :89:  :  :14:
      :5 &quot;&quot;&quot;)

_, dmask_msk, dmask_val = msk(&quot;&quot;&quot;  :  :  : f:8 :a5:d : 2: 0:b :7 :  : 1:  : 4:
     1:0d:  :3 :  :6 :  :  : b:  :  :  :e :  :  :
    0e: 0:db:  :1a:1c:c0:  : e:  :  :99:bc:8 :a5:
    7 :7 :7 : b:  :  : 8: 8:  :7 :55: 2:  :  :f :
    b2:  :  :b :f :4 :  : 8:  :b :  :  :  : 0:  :
    0 :  :6 :9 :  :  :  : b: 4:  : 0: a: 5:07:b :
     9: c:9a: 9:  : 7:9e:  : b:60:f :  :  :  :0 :
      : 3:0 :  :  :  : 1:b :  :  : b: 6:0 :f :  :
      : 2:18: 6: b:1 :  :  :  :  :d3:f3:  :a :  :
     3:  :  :  :  : 3: d: 1: 2:7 :  : d:  : 2: d:
      :  : d:4 :  :d :  :6d: c:a :b6:  :  :  : 1:
    69:  : 7:  :89:  :c :8 :61: d:25: 3:7 :1b: 4:
    b :  :8 :55:  :49: 1:2 :3 :  :1 :e9:a8: 3:  :
    9 :  : 1:f8:d3:  :e :  :d :  :9 :b6:  :  :71:
    1 :  :c1:  : b: 1:  : 6:e :  :64:  :  :1a:c :
      : b:  :bf:c :  : 0:  : 8:a :4 :  :26:a :5 :
    6 :  :  :  :eb:  :e5: a:  :3e:f9:10:0 :  :  :
     6:0 :  : 8:  : 1:72: c:0 : f:5 : f:9c: 0: e:
     7:b :  :  :  :  :d9: 4:  : e:c :68:  :  :  :
     c:  :3a:  :  :a0:ea: 3: 4:  :72:a :d : 8:  :
      :0d:5 :0 : a: 7:c :bb: 6: 4:a :ce:d :2 : 1:
      :  :17:6 :  : c: b:  : f:  :3 : 5:6 :3 :0e:
      : 7:c :3e: 2: 9: 7: 6: f: e: f: 9:  :f3: 9:
    a :c1:6 :  : 1:9 :  :43:  : f: 5:  :0 :27: 4:
    4 :a :  :e9:  : 8: 4:3 :8a: 6:16:d5:c : e: e:
      :d : c:b :a8:  : 7:  : 9:  :7 :7d:  :  :  :
      :  :  :4 :2 :  : 3: 3: 6:  :  :  :7b:0 :  :
     e:  :0 :  :a :  : 5:  :  :  : 5:1 :82:c :0d:
    4 :2 :fd:36: 5:50:0 :  :  :d : f: 6:  :  :e :
    0 :  :  :ce:  :9e:8 :  :0 :d :07:b3:  :  :  :
    0 :e4:  :  :68:b :c :  : c:5 :  :  :3 : 7: 2:
     c:e0:  :5 :  :  :b4:  :ef: 7:  :1 :e : 0:f :
      :6 :  :  :  :e0:c :3 :  :  : 3:  : d:  :  :
     3: 3: c: a:  :b : a:71: 3: 0:a :  :4 :5d:  :
    0 :4 &quot;&quot;&quot;)

_, dpmask_msk, dpmask_val = msk(&quot;&quot;&quot;  : 3:2a:  : d:  :  :  :  :0 :1 : f:  :  : 6:
    1 :2 :1b:07: a:e :b :c5:58:7 :  :e8: 7: 1: c:
      : 1:b :a0: 4:0f:5 :67:  :3 :7 :6 :f9:  : c:
      :79: 0:1 :65:  :8 :  :99: d:d :  :2 :9 :0 :
     e:  :0 :  :  :  : d:  :d :7 :6 :a9: a:8b: b:
      :  : 7: a:37:  :  :7 :1 :6 :  :c2: 7:6 :b :
     e:  :  :  :  :  :  :b :3a:5 :  :  :  :  :  :
      :  :  :cd:8 :  : d:  :7 : 3:  : f:e : c:  :
      : a:  :c : f:c : 7:b :5 :  :  :2 :8 :8 :6 :
    0a: a:  :  :3 :db:  : 4:00:  : d:  :b : 5:  :
    20: 2: 5:  :82:  : 0: 6:  :8a:  :7 :  : 8:  :
     4: 1:  :  :  : 8:46:  :  :  :  :  : 0:f :c8:
    2 :  : c:7 :  : 1:  :  :2 : 0: 5:  :  : 1:9b:
     6:9 : 0:74:  :c :  :e :  :  :cb:b :3 :3 :  :
     2:  :  :47:  :2 : 0:5 :  :  : d: 6:83:  :  :
      :c7:  :  :0b:  :  : c:  :3 :8 :  :9 :4 : 7:
    5 :c0:fe:  :f9: 1:  :0 : e: 8:02:  : f:  :c :
    55:61&quot;&quot;&quot;)

_, dqmask_msk, dqmask_val = msk(&quot;&quot;&quot;  :0b:7 :4 :0 : 0:6 : 7:7e:  : 5:  : 7:  : a:
    a :d : 0: 6: 4:86:  :  :8 :  :  :  :  :e :8f:
     9:  :  :  : 1:  :2 :  : 7: b:1 :5 : f:  :8 :
      :d :21:  :e : d:  :c9:e : b:  :  :1 :  :  :
      :d :a2:b7:  :  :  :f3:  :42:  :e : c:  :f :
      : 0:f :7 : 4: 5:34:  :4 : c:  :  :8 :d : 8:
    5 :af: 3:1d: 5:4 :  :2 :  :6 :c : 6:a :1 :5 :
     a:9 :  :d :  :  :0a:a1:  :f :7 :9 :b :  :  :
     f:2 :27: f:  :0 :f6:4d:  :  :  :  :  :5 :  :
     4:08:  : 5:  : 8: 5:  :  :  :18: 4: 8:57: 2:
     f: a:  :  :a8: f: c:f : e: 1:9 :c : 4:9 :  :
      :  :  :  :  : 1:  :2 :  :d1:  : 6:e : d:  :
      : f:04:2 :8d:  : 3:  :  :b : 8:  :d6:  : 2:
      :  :  :6 :  : f:  :  : 0:6 :  :51:  :48:19:
      :  :  :69:4 : c:  :c :  : f:  :f4:d :  : f:
     d:0 :0d:b :3 : 3:2 :  :  :6 : b:5 :2 :  : c:
     1:5a: f:f :  :  :7e:3e:  :d :f :0 : d: c: 6:
     1&quot;&quot;&quot;)


def search(K, Kp, Kq, check_level, break_step):
    max_step = 0
    cands = [0]
    for step in range(1, break_step + 1):
        #print &quot; &quot;, step, &quot;( max =&quot;, max_step, &quot;)&quot;
        max_step = max(step, max_step)

        mod = 1 &lt;&lt; (4 * step)
        mask = mod - 1

        cands_next = []
        for p, new_digit in product(cands, p_ranges[-step]):
            pval = (new_digit &lt;&lt; ((step - 1) * 4)) | p

            if check_level &gt;= 1:
                qval = solve_linear(pval, N &amp; mask, mod)
                if qval is None or not check_val(qval, mask, qmask_msk, qmask_val):
                    continue

            if check_level &gt;= 2:
                val = solve_linear(E, 1 + K * (N - pval - qval + 1), mod)
                if val is None or not check_val(val, mask, dmask_msk, dmask_val):
                    continue

            if check_level &gt;= 3:
                val = solve_linear(E, 1 + Kp * (pval - 1), mod)
                if val is None or not check_val(val, mask, dpmask_msk, dpmask_val):
                    continue

            if check_level &gt;= 4:
                val = solve_linear(E, 1 + Kq * (qval - 1), mod)
                if val is None or not check_val(val, mask, dqmask_msk, dqmask_val):
                    continue

                if pval * qval == N:
                    print(&quot;Kq =&quot;, Kq)
                    print(&quot;pwned&quot;)
                    print(&quot;p =&quot;, pval)
                    print(&quot;q =&quot;, qval)
                    p = pval
                    q = qval
                    d = invmod(E, (p - 1) * (q - 1))
                    coef = invmod(p, q)

                    print (RSA.construct(map(int, (N, E, d, p, q, coef))).exportKey())
                    quit()

            cands_next.append(pval)

        if not cands_next:
            return False
        cands = cands_next
    return True



def check_val(val, mask, mask_msk, mask_val):
    test_mask = mask_msk &amp; mask
    test_val = mask_val &amp; mask
    return val &amp; test_mask == test_val


# K = 4695
# Kp = 15700
# Kq = 5155

for K in range(1, E):
    if K % 100 == 0:
        print (&quot;checking&quot;, K)
    if search(K, 0, 0, check_level=2, break_step=20):
        print (&quot;K =&quot;, K)
        break

for Kp in range(1, E):
    if Kp % 1000 == 0:
        print (&quot;checking&quot;, Kp)
    if search(K, Kp, 0, check_level=3, break_step=30):
        print (&quot;Kp =&quot;, Kp)
        break

for Kq in range(1, E):
    if Kq % 100 == 0:
        print (&quot;checking&quot;, Kq)
    if search(K, Kp, Kq, check_level=4, break_step=9999):
        print (&quot;Kq =&quot;, Kq)
        break

</code></pre>
<h4 id="最优非对称加密填充"><a class="header" href="#最优非对称加密填充">最优非对称加密填充</a></h4>
<pre><code class="language-python">from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

with open('pubkey.pem', 'r') as f:
    key = RSA.importKey(f)
    N = key.n
    e = key.e

print(N)
print(e)

with open('private.pem', 'r') as f:
    private = RSA.importKey(f)
    oaep = PKCS1_OAEP.new(private)

with open('flag.enc', 'r') as f:
    print(oaep.decrypt(f.read()))
</code></pre>
<h2 id="已知p-q-e-求-n"><a class="header" href="#已知p-q-e-求-n">已知p q e 求 n</a></h2>
<pre><code class="language-python"># 已知p q e 求 n

# 在一次RSA密钥对生成中，假设p=473398607161，q=4511491，e=17

import gmpy2
p = 473398607161
q = 4511491
e = 17
n = (p-1)*(q-1)
d = gmpy2.invert(e,n)
print(d)
</code></pre>
<h2 id="附2rsa综合性题集"><a class="header" href="#附2rsa综合性题集">附2:RSA综合性题集</a></h2>
<h2 id="附3参考资料"><a class="header" href="#附3参考资料">附3:参考资料</a></h2>
<p>RSA知识大纲：https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_theory-zh/</p>
<p>大质数在线分解数据库：http://factordb.com</p>
<p>一类RSA：https://www.jianshu.com/p/0272069cb936?utm_campaign=maleskine</p>
<p>对模数N的一些小结：https://nonuplebroken.com/2018/11/26/RSA模数相关攻击/#原理</p>
<p>Jarvis-OJ-Crypto: https://skysec.top/2017/12/11/Jarvis-OJ-Crypto/#very-hard-RSA</p>
<p>对RSA的总结1：https://zhuanlan.zhihu.com/p/76228394</p>
<p>对RSA的总结2：https://xz.aliyun.com/t/6459#toc-59</p>

                    </main>

                    <nav class="nav-wrapper" aria-label="Page navigation">
                        <!-- Mobile navigation buttons -->
                            <a rel="prev" href="../../posts/ctf/3.1_Crypto.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                                <i class="fa fa-angle-left"></i>
                            </a>

                            <a rel="next" href="../../posts/ctf/3.5_Base64.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                                <i class="fa fa-angle-right"></i>
                            </a>

                        <div style="clear: both"></div>
                    </nav>
                </div>
            </div>

            <nav class="nav-wide-wrapper" aria-label="Page navigation">
                    <a rel="prev" href="../../posts/ctf/3.1_Crypto.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                        <i class="fa fa-angle-left"></i>
                    </a>

                    <a rel="next" href="../../posts/ctf/3.5_Base64.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                        <i class="fa fa-angle-right"></i>
                    </a>
            </nav>

        </div>



        <script>
            window.playground_line_numbers = true;
        </script>

        <script>
            window.playground_copyable = true;
        </script>

        <script src="../../ace.js"></script>
        <script src="../../editor.js"></script>
        <script src="../../mode-rust.js"></script>
        <script src="../../theme-dawn.js"></script>
        <script src="../../theme-tomorrow_night.js"></script>

        <script src="../../elasticlunr.min.js"></script>
        <script src="../../mark.min.js"></script>
        <script src="../../searcher.js"></script>

        <script src="../../clipboard.min.js"></script>
        <script src="../../highlight.js"></script>
        <script src="../../book.js"></script>

        <!-- Custom JS scripts -->
        <script src="../../src/js/custom.js"></script>


    </div>
    </body>
</html>
